史丰收速算
史丰收速算法的革命性贡献是：从高位算起，预测进位。不需要九九表，彻底颠覆了传统手算!
速算的核心基础是：1位数乘以多位数的乘法。
其中，乘以7是最复杂的，就以它为例。
因为，1/7 是个循环小数：0.142857...，如果多位数超过 142857...，就要进1
同理，2/7, 3/7, ... 6/7 也都是类似的循环小数，多位数超过 n/7，就要进n
下面的程序模拟了史丰收速算法中乘以7的运算过程。
乘以 7 的个位规律是：偶数乘以2，奇数乘以2再加5，都只取个位。
乘以 7 的进位规律是：
满 142857... 进1,
满 285714... 进2,
满 428571... 进3,
满 571428... 进4,
满 714285... 进5,
满 857142... 进6
请分析程序流程，填写划线部分缺少的代码。
这是一道代码填空题。代码填空题，读题非常重要，理解题意后按照题目思路一步步分析代码，必要的时候可以在调用相应函数时取恰当的参数来debug一下。下面是等待填空的代码：
1 //计算个位 2 int ge_wei(int a) 3 { 4 if(a % 2 == 0) 5 return (a * 2) % 10; 6 else 7 return (a * 2 + 5) % 10; 8 } 9 10 //计算进位 11 int jin_wei(char* mod) 12 { 13 char* level[] = { 14 "142857", 15 "285714", 16 "428571", 17 "571428", 18 "714285", 19 "857142" 20 }; 21 22 char buf[7]; 23 buf[6] = ' '; 24 strncpy(buf,mod,6); 25 26 int i; 27 for(i=5; i>=0; i--){ 28 int tr = strcmp(level[i], buf); 29 if(tr<0) return i+1; 30 while(tr==0){ 31 mod += 6; 32 strncpy(buf,mod,6); 33 tr = strcmp(level[i], buf); 34 if(tr<0) return i+1; 35 ______________________________; //填空 36 } 37 } 38 39 return 0; 40 } 41 42 //多位数乘以7 43 void f(char* s) 44 { 45 int head = jin_wei(s); 46 if(head > 0) printf("%d", head); 47 48 char* mod = s; 49 while(*mod){ 50 int a = (*mod-'0'); 51 int x = (ge_wei(a) + jin_wei(mod+1)) % 10; 52 printf("%d",x); 53 mod++; 54 } 55 56 printf(" "); 57 } 58 59 int main() 60 { 61 f("428571428571"); 62 dfs("34553834937543"); 63 return 0; 64 }
整体很清晰，有一个计算个位的函数，一个计算进位的函数，还有一个就是计算并打印多位数乘以7的结果的函数。
先来分析计算多位数乘以7的函数，这个函数体现了计算的核心流程：
1 //多位数乘以7 2 void f(char* s)//s代表多位数 3 { 4 int head = jin_wei(s);//head是s的进位 5 if(head > 0) printf("%d", head);//输出进位 6 7 char* mod = s;//拷贝字符串指针 8 while(*mod){//没有到末尾 9 int a = (*mod-'0');//依次字符转数字 10 int ge = ge_wei(a);//算出个位 11 int jin = jin_wei(mod + 1);//后续字符串的进位 12 int x = (ge + jin) % 10;//两者相加取个位 13 printf("%d",x);//打印 14 mod++;//指针后移 15 } 16 17 printf(" "); 18 }
传进来的参数char* s就是代表多位数的字符串。先计算该多位数的进位，如果进位存在（>0）就输出；接着不断读取字符直到字符串末尾，每次都先把字符转成数字，然后计算该位的个位结果和从后一位开始的多位数的进位，把两者加起来取个位，即得到该位的正确结果并输出。
计算个位的函数非常简单，和题意完全一致：偶数乘以2，奇数乘以2再加5，都只取个位。下面来分析需要填空的计算进位的函数：
1 //计算进位 2 int jin_wei(char* mod) 3 { 4 char* level[] = { 5 "142857", 6 "285714", 7 "428571", 8 "571428", 9 "714285", 10 "857142" 11 };//多位数超过 n/7，就要进n 12 13 char buf[7]; 14 buf[6] = ' '; 15 strncpy(buf,mod,6);//将mod这个字符串的前6个字符，拷贝到buff中 16 17 int i; 18 for(i=5; i>=0; i--){ 19 int tr = strcmp(level[i], buf);//从后往前，依次level中的串和buff比较 20 if(tr<0)//buff更大 ，得出了进位数=i+1 21 return i+1; 22 while(tr==0){//buff和level[i]相同了 23 mod += 6;//往后偏移6位 24 strncpy(buf,mod,6);//再拷贝6个字符到buff中 25 tr = strcmp(level[i], buf);//再比较 26 if(tr<0) return i+1;//buf更大 27 // ______________________________; //填空 28 // //?//buff更小 29 if(tr>0) return i; 30 31 } 32 } 33 34 return 0; 35 }
其实把题目读懂了，真的很好理解代码，填空也很轻松。我就是一开始没有好好读题，做这道题卡了半天....
很简单，再来读一遍题目：1/7 是个循环小数：0.142857...，如果多位数超过 142857...，就要进1。一开始没认真读，后来才发现这是一个六位一循环的小数，所以只要一个多位数比这个循环数142857大，它的最高位就要进1；比它小就不用进位，即进0。比如142857*7=999999，最高位没有进位，结果还是一个六位数；但如果是142858，那么最高位就要进1，结果算出来会是一个七位数。又因为这是六位一循环的数，所以如果这个多位数的前六位和循环数142857一样大，我们还需要比较后面的数，才能知道它到底是不是比这个循环数大，并且每次都还是六位六位的来比较；如果后面的数字比这个六位数大，就说明多位数大于这个循环数，需要进1；如果后面的数字比这个数字小呢，就说明还没达到这个进位要求，进0即可。类比到2/7、3/7、n/7...如果比循环数大，就进n；比它小，就进n-1。这样想明白之后，再来分析代码和填空就都很简单了。
把标志进位的数按顺序放进数组 level[] 中，将待乘的多位数的前六位和 level[i] 比较；先从最大的数 level[5] 开始比较，如果比它小，则 i-- ，继续和level[i]比较；如果比 level[i] 大，则按照对应数字进位，刚好是进 i+1 ；如果和 level[i]大小一样，则指针向后移动六位，再继续和后面的六位数字比较，如果还是相同就继续后移六位，直到不再一样为止：比 level[i]大，就说明满足进位条件，还是进 i+1；比 level[i]小，说明不满足进位条件，进 i 即可。所以此处我们应填 if(tr>0) return i;