首页 > 代码库 > Project Euler——13.Larger Sum总结

Project Euler——13.Larger Sum总结

  今天花了一天的时间在Linux 系统上完成了欧拉计划第13题的Larger Sum编程(花费的时间有点长啊)。既然耗了这么长的时间,那就要好好的总结一下,不然也对不起这一天的时间。这次主要是在ubantu 上编程,简单的设计到了编译、调试、链接和简单的编写Makefile。

  Larger Sum 中涉及到了超大数(50位)的计算,在C编译语言中,int 为32位,最大的整数long long int也只有pow(2,64)大约19位,这样完全不能用简单的四和运算来求和。于是代码中,我使用字符串的每位累加来求和。代码中最主要的几点如下:

  1、 怎样获取100*50 个数: 

    对于100个50位的整数,代码中采用文本的的方式,使用read读取每行的文本到二维数组string[100][51]中。代码中使用了open创建Larger_sum.txt的文件描述符,使用creat 创建不存在的cc.txt文本(用于判断是否能够正常的读取文本中的100个50位数)。

  2、求和100个50位数的算法:

    对于100个50位的数,代码中采用二维数组的方式,从低位依次对100个数进行求和,如string[i][0]+string[i][1]+...+srting[i][49]+ 商值,再进行取余、求商。每次运算的余数保存在int NewStr[51]的整型数组中,最后一次运算的商值则保持在NewStr[50]中。

  3、简单编写Make file:

    all:main.o

      gcc -o all main.c

    clean:

      rm all main.o

  注意:1、在代码运行过程中,出现了warning:function returns address of local variable, 翻译过来为 “警告:本地函数返回的地址”。这是由于Cal_Digit函数中,代码没有给返回的指针数值分配固定的地址,而该函数中的局部变量在执行完后,会自动释放分配的内存。导致在主函数中调用失败。代码中使用malloc分配固定的内存,再在代码执行完之前释放内存。

      2、warning: incompatible implicit declaration of built -in function [ enable by default], 这是用于调用了公共函数没有声明头文件 string.h 和stdlib.h。

      3、在Linux 下怎样精确的计算程序执行的时间。可以通过三个函数来实现:

                 1)clock()函数;其声明的定义在time.h 头文件中

        2)time()函数;

        3)gettimeofday()函数;

 1 #include <string.h>
 2 #include <stdlib.h>
 3 #include <time.h>
 4 
 5 int *Cal_Digit(char *string);
 6 int main()
 7 {
 8     //read 100*50 digit into string
 9     int fp, fp1;
10     static int i = 0;
11     static int j = 0;
12     char string[100][51]= {0};
13     int *result;
14     clock_t time1,time2;
15     time1 = clock();
16     if((fp=open("//home//yb//test//Project_Euler//13.Larger_sum//Larger_sum.txt", 0, 0)) ==  -1)
17     {
18         printf("OPEN FILE ERROR\n");
19     }
20     creat("//home//yb//test//Project_Euler//13.Larger_sum//cc.txt");
21     if((fp1=open("//home//yb//test//Project_Euler//13.Larger_sum//cc.txt", 2, 0)) ==  -1)
22     {
23         printf("OPEN FILE ERROR\n");
24     }
25     while( read(fp, string[i], 51) > 0)
26     {
27         write(fp1, string[i], 51);
28         i++;
29     }
30     close(fp);
31     close(fp1);
32 
33     //calculate 100*50 digit
34     printf("Calcutate:\n");    
35     result = Cal_Digit(&string[0][0]);
36 
37     //printf result
38     for(i=50; i>=0;i--)
39     {
40         printf("%d", *(result+i));
41     }
42     free(result);
43     time2 = clock();
44     printf("\nRun Time:%fs \n", (double)(time2-time1)/CLOCKS_PER_SEC);
45     return 0;
46 }
47 int *Cal_Digit(char *string)
48 {
49     int *NewStr;
50     int i =0 , j=0;
51     int z =0;
52     int temp =0;
53     int CarryBit = 0;
54     NewStr = (int*)malloc(sizeof(int)*50);
55 
56     for(i=49; i>=0; i--)
57     {
58         temp = CarryBit;
59         for(j=0; j<100; j++)
60         {
61             temp += *(string + j*51 + i) - 48;
62         }
63         NewStr[49-i]= temp%10;
64         CarryBit = temp/10;
65         if(i == 0)
66         {
67             NewStr[50] = CarryBit;
68         }
69     }
70     return NewStr;
71 }

 

Project Euler——13.Larger Sum总结