大数运算
struct bign{
int d[maxn];//底位存储num的底位
int len;
}
大数加法
bign add(bign n1,bign n2){
bign c;
c.len = 0;
int carry = 0；
for(int i=0;i<n1.len||i<n2.len;i++){
int temp = n1.d[i]+n2.d[i] + carry;
c.d[c.len++] = temp%10;
carry /=10;
}
if(carry != 0){
c.d[len++] = carry;
}
return c;
}
延迟回文数（PAT basic level B1097）
题目链接：
https://pintia.cn/problemsets/994805260223102976/problems/994805261754023936
思路：
- 设结构体倒着存储num和num的长度
- 写一个bign_reverse()返回一个bign的reverse，注意要重新计算长度
- 写一个判断bign是否回文数的函数，设一个cnt判断循环次数
- 根据加法法则写一个add函数
代码
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
struct bign
{
int d[10000];
int len;
bign() {
memset(d, 0, sizeof(d));
len = 0;
}
};
bign change(string num) {
bign b;
b.len = num.size();
for (int i = 0; i < b.len; i++)
{
b.d[b.len - i - 1] = num[i] - '0';
}
return b;
}
bool isplid(bign b) {
int i = 0, j = b.len - 1;
while (i < j) {
if (b.d[i] != b.d[j]) {
return false;
}
i++;
j--;
}
return true;
}
bign add(bign b1, bign b2) {
bign c;
c.len = 0;
int carry = 0;
for (int i = 0; i < b1.len || i < b2.len; i++)
{
int temp = b1.d[i] + b2.d[i] + carry;
c.d[c.len++] = temp % 10;
carry = temp / 10;
}
if (carry != 0) {
c.d[c.len++] = carry;
}
return c;
}
void print(bign b) {
for (int i = b.len-1; i >=0; i-- )
{
printf("%d",b.d[i]);
}
}
bign bign_reverse(bign b) {
bign ans;
for (int i = 0; i < b.len; i++)
{
ans.d[i] = b.d[b.len - i - 1];
}
int j = b.len - 1;
while (ans.d[j] == 0) {
j--;
}
ans.len = j + 1;
return ans;
}
int main()
{
string num;
int cnt = 0;
cin >> num;
bign b1 = change(num);
while (!isplid(b1)&& cnt++ != 10) {
print(b1);
printf(" + ");
bign b2 = bign_reverse(b1);
print(b2);
bign sum = add(b1, b2);
printf(" = ");
print(sum);
printf("
");
b1 = sum;
}
if (isplid(b1) && cnt < 10) {
print(b1);
printf(" is a palindromic number.");
}
else {
printf("Not found in 10 iterations.");
}
}
大数减法
bign minus(bign n1,bign n2){
bign c;
c.len = 0;
for(int i=0;i<n1.len||i<n2.len;i++){
if(n1.d[i] < n2.d[i]){//不够减
n1.d[i+1]--;
n1.d[i]+=10;
}
c.d[c.len++] = n1.d[i] - n2.d[i];
}
//除去高位的0，重新算len
while(c.len-1>=1&&c.d[c.len-1]==0){
c.len--;
}
return c;
}
大数与int乘法
bign mutify(bign n,int x){
bign c;
c.len = 0;
int carry = 0;
for(int i=0;i<n.len;i++){
int temp = n.d[i] * x + carry;
c.d[c.len++] = temp %10;
carry = temp /10;
}
while(carry !=0){
c.d[c.len++] = carry%10;
carry=temp / 10;
}
return c;
}
1.清华大学机试（N的阶乘）1<N<=1000
大数与int的除法
bign divide(bign num,int x,int &r){//r为余数，当不能整除时，余数存在这
bign c;
c.len = num.len;
r = 0;
//从高位开始除
for(int i=num.len-1;i>=0;i--){
int r = num.d[i] + r * 10; //被除数的当前位
if(num.d[i] < x){//被除数当前位不够除
c.d[i]=0;
}else{
c.d[i] = r /x;
r = r % x;
}
}
while(c.len-1>1&&c.d[c.len-1]==0)
c.len--;
return c;
}
1.10进制vs 2进制（清华大学机试）一题顶三题
https://www.nowcoder.com/practice/fd972d5d5cf04dd4bb4e5f027d4fc11e?tpId=40&tqId=21357&tPage=2&rp=2&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking
思路：输入为最多1000位的十进制数n，将用大数除法思路变成2进制，再reverse，再将其变成十进制。（有点烦....)
代码：
#include <iostream>
#include <string.h>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 1010;
struct bign
{
int d[maxn], len;
bign() {
len = 1;
memset(d, 0, sizeof(d));
}
};
bign change(string num) {
bign c;
c.len = num.size();
for (int i =c.len-1; i >=0 ; i--)
{
c.d[c.len - i - 1] = num[i]-'0';
}
return c;
}
bign divide(bign num, int x,int &r) {
bign c;
c.len = num.len;
//从高位开始除
for (int i = num.len - 1; i >= 0; i--) {
r = num.d[i] + r * 10; //被除数的当前位
if (r < x) {//被除数当前位不够除
c.d[i] = 0;
}
else {
c.d[i] = r / x;
r = r % x;
}
}
while (c.len - 1 >= 1 && c.d[c.len - 1] == 0)
c.len--;
return c;
}
vector<int> ten22(bign num) {//将num变成2进制，逆置后存储在vc中
vector<int > vc;
while (!(num.len == 1 &&num.d[0] == 0)) {
int r = 0;
num = divide(num, 2, r);
vc.push_back(r);
}
reverse(vc.begin(), vc.end());
while (vc[vc.size() - 1] == 0) {//去零头
vc.pop_back();
}
return vc;
}
bign mutify(bign n, int x) {
bign c;
c.len = 0;
int carry = 0;
for (int i = 0; i < n.len; i++) {
int temp = n.d[i] * x + carry;
c.d[c.len++] = temp % 10;
carry = temp / 10;
}
while (carry != 0) {
c.d[c.len++] = carry % 10;
carry /= 10;
}
return c;
}
bign add(bign n1, bign n2) {
bign c;
c.len = 0;
int carry = 0;
for (int i = 0; i < n1.len || i < n2.len; i++) {
int temp = n1.d[i] + n2.d[i] + carry;
c.d[c.len++] = temp % 10;
carry = temp / 10;
}
if (carry != 0) {
c.d[c.len++] = carry;
}
return c;
}
bign two1010(vector<int> vc) {//将逆置的二进制转换会bign。。。。感觉最难这里。。。。。
bign ans;
ans.d[0] = 0;
ans.len = 1;
bign product;//基数
product.d[0] = 1;
product.len = 1;
for (int i = 0; i < vc.size(); i++)
{
if (vc[i] == 1) {
ans = add(ans, product);
}
product = mutify(product, 2);
}
return ans;
}
void show(bign num){
for (int i = num.len-1; i >=0 ; i--)
{
printf("%d", num.d[i]);
}
cout << endl;
}
int main()
{
string n;
while (cin>>n)
{
bign tar = change(n);
vector<int> vc = ten22(tar);
bign res = two1010(vc);
show(res);
}
}