转自  http://blog.csdn.net/justlinux2010/article/details/8931677

这个题目是群里贴出来的的，只有图片，题目如下：

解题思路：
很明显，这个题目如果直接计算11的n次方的值的话肯定不行，因为n的取值范围是0到1000，在C语言中即使用unsigned long也存储不了这么大的结果。
要解决这个问题，还是要从11这个数本身的特点入手。
我最开始的想法是展开（10+1）^n，然后从这个展开的式子中找到解题方法，但是展开的结果表示这个路子走不通，展开的结果中要计算阶乘，还要计算加法，这样的式子对解题来说没有帮助。
后来，就感觉这个每次乘以11的的结果比较特别，类似杨辉三角似的，所以在纸上开始手动计算11相乘的结果，发现了一个规律：假设现在的值为p（十进制表示），p乘以11的结果就是最低位仍为1，其他位都是p的相邻的两个数逐步相加的结果，当然最高位要做一下特殊处理，拿p的最高位加上进位（有可能两个数字相加的结果大于等于10），如下所示：
1
11
121
1331
14641
161051
1771561
19487171
214358881
2357947691
所以可以这样来解决这个问提：
1）申请两个长度为n（最终的值的十进制位个数不会超过n）的整数数组tmp，curr。tmp存储上个数的十进制表示，curr用来存储现在要计算的数的十进制表示。注意：数组中的每个元素存储的是十进制中的一位
2）循环遍历tmp、curr将各个元素初始化为-1.
3）因为要执行n次11相乘，所以外层循环的次数也是n，而内层循环的次数取决于上次的数的位数。循环计算当前数的值，也就是计算上个数乘以11的值
4）交换tmp、curr的值，然后检查是否执行完毕，否则重复执行第3步操作。
5）循环遍历tmp数组（因为3、4步骤中的循环结束时，tmp中存储的是最终的值），统计数组中1的个数，然后将结果返回
代码实现如下：
[cpp]  view plain copy
  1. #include <stdio.h>  
  2. #include <ctype.h>  
  3. #include <stdlib.h>  
  4.   
  5. void print_array(int *a, int n)  
  6. {  
  7.     int i;  
  8.   
  9.     for (i = n-1; i >= 0; --i) {  
  10.         printf("%d", a[i]);  
  11.     }  
  12.     printf("\n");  
  13. }  
  14.   
  15. int solution(int n)  
  16. {  
  17.     int *curr, *tmp;  
  18.     int tmp_len;  
  19.     int *p;  
  20.     int carry = 0;  
  21.     int i, j;  
  22.     int size = 2*n;  
  23.     int count = 0;  
  24.   
  25.     curr = malloc(sizeof(int) * size);  
  26.     if (!curr) {  
  27.         printf("Out of memory.\n");  
  28.         return -1;  
  29.     }  
  30.   
  31.     tmp = malloc(sizeof(int) * size);  
  32.     if (!tmp) {  
  33.         free(curr);  
  34.         printf("Out of memory.\n");  
  35.         return -1;  
  36.     }  
  37.   
  38.     for (i = 0; i < size; ++i) {  
  39.         curr[i] = -1;  
  40.         tmp[i] = -1;  
  41.     }  
  42.   
  43.     tmp_len = 0;  
  44.     for (i = 0; i < n; ++i) {  
  45.         carry = 0;  
  46.         curr[0] = 1;  
  47.   
  48.         for (j = 1; j < tmp_len; ++j) {  
  49.             curr[j] = tmp[j] + tmp[j - 1] + carry;  
  50.             carry = curr[j] / 10;  
  51.             curr[j] = curr[j] % 10;  
  52.         }  
  53.   
  54.         if (i > 0) {  
  55.             curr[j] = tmp[j - 1] + carry;  
  56.             if (curr[j] >= 10) {  
  57.                 curr[j] = curr[j] % 10;  
  58.                 curr[++j] = 1;  
  59.             }  
  60.             tmp_len = ++j;  
  61.         } else {  
  62.             tmp_len = 1;  
  63.         }  
  64.           
  65.         p = tmp;  
  66.         tmp = curr;  
  67.         curr = p;  
  68.     }  
  69.   
  70.     for (i = 0; i < size; ++i) {  
  71.         printf("%d", tmp[i]);  
  72.         if (tmp[i] == 1) {  
  73.             ++count;  
  74.         }  
  75.     }  
  76.     printf("\ncount = %d.\n", count);  
  77.   
  78.     free(tmp);  
  79.     free(curr);  
  80.     return 0;  
  81. }  
  82.   
  83. int main(void)  
  84. {  
  85.     solution(1000);  
  86.     return 0;  
  87. }  

Logo
Linux

更多推荐

网卡速率和双工模式的配置

http://linux.chinaitlab.com/system/792187.html1、mii-tool 配置网络设备协商方式的工具；    1.1 mii-tool 介绍；    mii-tool - view, manipulate media-independent interface status （mii-tool 是查看，管理介质的网络接口的状态）

avatar Linux

Linux虚拟文件系统之文件系统卸载（sys_umount())

Linux中卸载文件系统由umount系统调用实现，入口函数为sys_umount()。较于文件系统的安装较为简单，下面是具体的实现。1. /*sys_umont系统调用*/2. SYSCALL_DEFINE2(umount, char __user *, name, int, flags)3. {4.struct path path;

avatar Linux

Linux系统下超级终端Minicom的使用方法（例如：连接交换机，路由器等）转http://baike.baidu.com/view/2911642.htm?fr=ala0_1

<br />　　Linux系统下超级终端Minicom的使用方法 <br />　　Linux下的Minicom的功能与下的超级终端功能相似，适于在通过超级终端对设备的管理以及对嵌入操作系统的升级，现写出Minicom的使用手册： <br />　　1． 启动minicom <br />　　以root权限登录系统 <br />　　使用命令 <br />　　minicom –s 则minicom启动，屏

avatar Linux