算法技巧

1000-digit Fibonacci number The Fibonacci sequence is defined by the recurrence relation：Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1. Hence the first 12 terms will be: F1 = 1F2 = 1F3 = 2F4 = 3F5 = 5F6 = 8F7 = 13F8 = 21F9 = 34F10 = 55F11 = 89F12 = 144 The 12th term, F12, is the first term to contain three digits. What is the index of the first term in the Fibonacci sequence to contain 1000 digits? 1.大整数加法将两个数组循环相加——用指针将数组的地址作为函数参数传递到函数中，通过交换二维数组第一个下标交换数组地址 123456789101112131415161718192021222324252627282930313233343536373839404142/*思路：大整数加法 + 循环使用两个变量求fib数列1.将大整数加法封装在一个函数中2.循环使用两个变量(数组)求斐波那契数列项3.当出现某一项大于1000时，输出项数结束循环*/#include<iostream>using namespace std;//1.将大整数加法封装在一个函数中void func(int *n1, int *n2){ //注意：初始的n2可能比n1短，需要首先更新答案的长度 n2[0] = n1[0]; for(int i = 1; i <= n2[0]; ++i){ n2[i] += n1[i]; if(n2[i] > 9){ n2[i + 1] += n2[i] / 10; n2[i] %= ...

Large sum Work out the first ten digits of the sum of the following one-hundred 50-digit numbers. 37107287533902102798797998220837590246510135740250463769376774900097126481248969700780504170182605387432498619952474105947423330951305812372661730962991942213363574161572522430563301811072406154908250230675882075393461711719803104210475137780632466768926167069662363382013637841838368417873436172675728112879812849979408065481931592621691275889832738442742289174325203219235894228767964876702721893184745144573600130643909116721685684458871160315327670386486105843025439939619828917593665686757934951621764571418565606295021572231965867550793241933316490635246274190492910143244581382266334794475817892575867718337217661963751590579239728245598838407582035653253593990084026335689488301894586282278288018119938482628201427819413994056758715117009439035398664372827112653829987240784473053190104293586865155060062958648615320752733719591914205172558297169388870771546649911559348760353292171497005693854 ...

大整数运算 1.大整数加法 整数存储类型 范围 short（2 byte） - 215 ~ (215 - 1) int（4 byte） - 231 ~ (231 - 1) long long（8 byte） - 263 ~ (263 - 1) 使用字符串进行数字的输入 将数字拆分存储在数组中，num[0]存储数字长度，num[1]存储个位、num[2]十位、num[3]百位……以此类推==倒序存储== 按照==加法规则==将数组中对应的数字相加后存入结果数组中 对需要进位的数字进行进位 12345678910111213141516171819202122232425262728293031323334353637383940414243#include<iostream>#include<cstring>using namespace std;char s1[1005], s2[1005];//输入的两个数字存储在字符串中int num1[1005], num2[1005];//输入的两个数字转化存储在数组中int sum[1005];//数字相加后的结果存储数组int main(){ //1.使用字符串进行数字的输入 cin >> s1 >> s2; num1[0] = strlen(s1); num2[0] = strlen(s2); //2.将数字拆成一位位数字存储在数组中 for(int i = 0, j = num1[0]; s1[i]; ++i, --j){ num1[j] = s1[i] - '0'; } for(int i = 0, j = num2[0]; s2[i]; ++i, --j){ num2[j] = s2[i] - '0'; } //3.按照加法规则将数组中对应的数字相加后存入结果数组中 sum[0] = max(num1[0], num2[0]); for(int i = 1; i <= ...

Largest product in a grid In the 20×20 grid below, four numbers along a diagonal line have been marked in red. 08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 0849 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 0081 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 6552 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 9122 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 8024 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 5032 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 7067 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 2124 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 7221 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 9578 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 9216 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 5786 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 5819 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 4004 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 6688 3 ...