| 存储结构
//大整数类型 结构体 struct bign { int d[maxn]; int len; bign() { //构造函数初始化 len = 0; memset(d, 0, sizeof(d)); } };| 字符串 转为 大整数
//把字符串表示的大整数转换成bign类型 bign change(char str[]) { bign c; for(int i = strlen(str) - 1; i >= 0; i--) { //逆序保存，因为操作都是从低位到高位进行 c.d[c.len++] = str[i] - '0'; } return c; }| 大整数比较
//比较函数 （均正） int compare(bign a, bign b) { if(a.len > b.len) return 1; //a大 else if(a.len < b.len) return -1; //a小 else { for(int i = a.len - 1; i >= 0; i--) if(a.d[i] > b.d[i]) return 1; else if(a.d[i] < b.d[i]) return -1; return 0; //相等 } }| 高精度加法
/*高精度加法 思路：每一步: 将该位上的两个数与进位相加，结果的个位作为该位结果，十位作为新的进位 预处理：若一正一负，就转为做高精度减法；若两个负数，则绝对值相加，结果再补负号； */ bign add(bign a, bign b) { int carry = 0; bign c; for(int i = 0; i < a.len || i < b.len; i++) { //以较长的为界限（较短的高位全为0） int temp = a.d[i] + b.d[i] + carry; c.d[c.len++] = temp % 10; carry = temp / 10; } if(carry != 0) { //最后还有进位，直接赋值给最高位 c.d[c.len++] = carry; } return c; }| 高精度减法
//高精度减法 /* 思路：从低位开始，每一位判断是否够减，够减直接减，不够减从高一位借1（高位减1，被减位加10） 最后记得消去差的前导零 并 至少保留一位； 预处理 ：如果被减数<减数，则交换变量，最后加负号； */ bign minus(bign a, bign b) { //默认a > b ;且均非负 (其他情况使用前先做预处理) int carry = 0; bign c; for(int i = 0; i < a.len || i < b.len; i++) { if(a.d[i] < b.d[i]){ a.d[i + 1]--; a.d[i] += 10; } c.d[c.len++] = a.d[i] - b.d[i]; } while(c.len - 1 > 0 && c.d[c.len - 1] == 0) c.len--; return c; }| 高精度 * 低精度
/* 高精度 * 低精度 思路：用高精度的每一位去乘低精度整体，再与进位相加，所得结果的个位作为该位结果， 其他高位所有部分作为新的进位 预处理：若有负数，则记录负号，取他们的绝对值带入运算 */ bign multi(bign a, int b) { int carry = 0; bign c; for(int i = 0; i < a.len; i++) { int temp = b * a.d[i] + carry; c.d[c.len++] = temp % 10; carry = temp / 10; } while(carry != 0){ //乘法进位不止是个位数 c.d[c.len++] = carry % 10; carry /= 10; } return c; }| 高精度 / 低精度
/*高精度除法 思路：每一步：(上一步的余数*10 + 该步的位）作为被除数，够除则除，不够除商零； 最后：记得消去商中的前导零，同时至少保留一位 预处理： 函数中多传一个参数引用，用于返回余数 （设为全局变量也行） */ bign divide(bign a, int b, int& r) { //r记录最后的余数 bign c; c.len = a.len; //被除数和商的每一位是一一对应的，因此先令长度相等 for(int i = a.len - 1; i >= 0; i--) { r = r * 10 + a.d[i]; //和上一位余数组成被除数 if(r < b) c.d[i] = 0; //不够除，商0 else { //够除 c.d[i] = r / b; //商 r = r % b; //新余数 } } //消去商中的前导零 同时至少保留一位 while(c.len - 1 > 0 && c.d[c.len - 1] == 0) c.len--; return c; }| 输出大整数
//输出 void print(bign a) { for(int i = a.len - 1; i >= 0; i--) printf("%d", a.d[i]); //注意:最后并没有输出换行 }应用样例：大整数除以int，返回商和余数
int main() { char str[1010]; int k, r; scanf("%s %d", str, &k); bign a = change(str); a = divide(a, k, r); print(a); printf(" %d\n", r); return 0; }* * * ——— 整理自《算法笔记》 ———-
待整理：POJ - 1220
【转自discuss】
【精简版】
int i,l,k,a,b,T,t[555],A[555]; char s[555],d[555]; main(){ for(scanf("%d",&T);T--;){ scanf("%d%d%s",&a,&b,s); for(k=i=strlen(s);0<i--;) t[k-1-i]=s[i]-(s[i]<58?48:s[i]<97?55:61); for(l=0;k;){ for(i=k;1<i--;){ t[i-1]+=t[i]%b*a; t[i]/=b; } A[l++]=t[0]%b; t[0]/=b; for(;0<k&&!t[k-1];k--); } for(d[l]=i=0;i<l;i++) d[l-1-i]=A[i]+(A[i]<10?48:A[i]<36?55:61); printf("%d %s\n%d %s\n\n",a,s,b,d); } }【解释版】
/* Problem: POJ.1220 number base conversion Time: 2017//3/12 题意：可选符号[0-9,A-Z,a-z],其中[A-Z]表示[10-35],[a-z]表示[36-61] */ #include<stdio.h> #include<string.h> #include<iostream> /* * 任意进制转换: 其过程跟十进制 转 二进制一样 * 先将数除2，得出的余数为二进制的一位，大神将商直接保存在原来的数组里面 * 当长度为0，即商为0时，结束。其他进制之间的转换同理。 */ const int maxn = 1000; int B[maxn]; // 保存转换前 旧进制 下的每一位整数值(10进制) int A[maxn]; //保存转换后 新进制 下每一位整数值(10进制)？？ char original_str[maxn]; //保存读入的原始字符串 char new_str[maxn]; //保存转换后的字符串 int old_system, new_system; //要转换的两种进制 void solve() { int i, len, k; len = strlen(original_str); //字符串转为 int 逆序 数组 for(i = len; i >= 0; --i) { //[注意a-z表示36-61] B[len - 1 - i] = original_str[i] - (original_str[i] < 58 ? 48 : original_str[i]<97?55:61); } //为什么最高位还要转换？B[-1]不会越界吗？ for(k = 0; len > 0;) { /*作用： 截取B[]的一位(高位)，以新进制保存在A[] * 从高位（B的末尾）依次把每一位先对新进制取余（本位表示不了？那为什么要传给低位呢？因为A[k]从低往上递增， * 这样多出的部分会最后累加在B[0]中，最后会赋值给在新的A[k]）， * 再乘以旧进制，累加给前一位（相当于低位），(相当于把多余的数值从高位蜕下来了，一步步的保存在了A[]中) * 最后得到的是： 用新进制除得的商 * 一次循环，得到一位数，保存在A[k]中 */ for(i = len; i >= 1; --i) { //B[len] = 0 ？ //B已然是逆序了，为什么这儿有逆序操作，与其这样，之前为什么要保存成逆序？？ // 这样B末尾（相当于高位）可以缩短（截取后，最高位数值变为0） B[i-1] += (B[i] % new_system * old_system); B[i] /= new_system; } A[k++] = B[0] % new_system; B[0] /= new_system; while(len > 0 && !B[len-1]) //消去高位0 同时保持至少有一位 len--; //一位一位把B[]截取完（就是十进制转二进制的竖式除法的推广） } //清空最后一个字符，作为新字符串结束的边界（覆盖上一轮保存的值） new_str[k] = NULL; for(i=0; i<k; i++) //把A中保存的int转换为char new_str[k-1-i] = A[i] + (A[i] < 10 ? 48: A[i] < 36 ? 55 : 61); } int main() { int num_of_input; // freopen("in.txt","r",stdin); scanf("%d",&num_of_input); while(num_of_input--) { scanf("%d%d%s", &old_system, &new_system, original_str); solve(); printf("%d 进制: %s\n%d 进制: %s\n\n", old_system, original_str, new_system, new_str); } system("pause"); return 0; }