/*******對讀者說（哈哈如果有人看的話23333）哈哈大杰是華農的19級軟體工程新手，才疏學淺但是秉著校科聯的那句“主動才會有故事”還是大膽的做了一下建一個卑微博客的嘗試，想法自己之后學到東西都記錄一下
自己學的同時或許（我說或許啊哈哈）能幫到博友，如果有啥錯誤的話還請各位大佬在下面留言懟我，指出我的錯誤所在，我一定更改哈哈，一般記錄的都是我對一個知識點或者是一個演算法專題的筆記和一些在博客園里面看到寫的好的大佬的一些借鑒
文章大部分都是在codeblocks里面寫好了然后復制過來的，所以就有很多///***的，對你的產生困擾，深感抱歉
********/
//對自己說：堅持堅持堅持，總會有識訓，主動就會有故事！
//分割線------------------------------------------------------------本文借鑒https://www.cnblogs.com/orchidzjl/p/4287027.html（原文）
/********************
菲波數
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 12716 Accepted Submission(s): 4352
f(1)=f(2)=1
f(n)=f(n-1)+f(n-2) n>=3，
計算第n項Fibonacci數值，
Input 輸入第一行為一個整數N，接下來N行為整數Pi（1<=Pi<=1000），
Output 輸出為N行，每行為對應的f(Pi)，
Sample Input 5 1 2 3 4 5
Sample Output 1 1 2 3 5
思路：很純粹的高進度加法
基礎板子
//一般Fibonacci數在第一千多個的時候的值其實就已經達到了一百多位了，一般就10的一百多次方了
這種高位數就自然用陣列來存放也就是利用高精度加法了，然后由于是要輸入一個值n，然后輸出的是第
個fabonacci數的，所以就要用一個map原理
在c里面就自然的用到了二維陣列來存放了，就是一維陣列的下標就是這個n，然后這個一維陣列的元素組成就是第
n個數了
一般遇到差不多一千多位的fabonacci數的化就要建立一個陣列是a[1010][1010]
其實一千位的fabonacci數也就差不多幾百位，這里建立一千多位其實是浪費的，如果是要節省空間的化還是
就建立一個大菲波數 ---【杭電-HDOJ-1715】
a[1010][500]就差不多了
int ans[1010][500]//裝答案的/由于會用在高精度計算的函式里面也會在主函式里面用到的，所以就定義位全域變數就可以了
int c[500],d[500];由于只是在高精度函式里面用到這兩個陣列的所以最好還是不要定義位全域變數了，節省空間，裝第n-1個的fabonacci和第n-2個的fabonacci的，然后兩個用遞回來相加，用到高精度計算了
int n,m,i,j,k;//n是記錄a陣列的長度的，m是記錄b陣列長度的，ijk是用來回圈的，同樣的也是在函式里面喲ing到了的，不要定義位全域了
大菲波數
2019.11.25.9.18
*****************/
1 代碼： 2 /* 3 #include <stdio.h> 4 #include <stdlib.h> 5 #include<string.h> 6 char ans[1010][500]; //優化：ans用char比用int要節省空間，然后c陣列和d陣列由于是要進行計算的要除以10和對10取模的所以是要定義位int 7 //所以就要注意在型別上的轉化比如如果是char變成int的化就要-'\0'如果是int變成char的化就要+'\0' 8 void bigplus(char a[],char b[],int t) //這里的t表示的是第幾個fabonacci數的，然后a和b其實就是遞回里面用到的第n-1項和第n-2項的 9 { 10 int c[500]; 11 int d[500]; 12 memset(c,0,sizeof(c));memset(d,0,sizeof(d)); 13 int n,m,i=1,j=1,k; 14 n=strlen(a); 15 m=strlen(b); 16 for(k=n-1;k>=0;k--) //這些就沒什么好決議的了，在oj是實驗題里面就有高精度計算的水題了，或者在網上差一下給高精度計算的板子就會了 17 //不同的是oj上面的是用到了一個e來作為余數的就是 18 //c[i]=(a[i]+b[i]+e)%10; 19 // e=(a[i]+b[i])/10;//其實用這個方法是更省了d這個陣列的空間的了,不過我就是看到下面那個c[i+1]+=..這一步不同然后想積累一下別的方法才寫的hah1 20 21 22 { 23 c[i++]=a[k]-'0'; 24 } 25 for(k=m-1;k>=0;k--) //開始我搞錯了邊了了，k=n-1然后列印出來的結果就多了很多其他的符號呢 26 { 27 d[j++]=b[k]-'0'; 28 } 29 k=n>m?n:m; 30 for(i=1;i<=k;i++) 31 { 32 c[i+1]+=(c[i]+d[i])/10; 33 c[i]=(c[i]+d[i])%10; 34 } 35 if(c[k+1]) 36 k+=1; 37 j=0; 38 for(i=k;i>=1;i--) 39 ans[t][j++]=c[i]+'0'; 40 41 } 42 int main() 43 { 44 memset(ans,'\0',sizeof(ans)); //由于是ans是不可以初始化為0或者是其他陣列的不然之后列印的時候就會把后面的陣列也列印出來了 45 // 所以就要對ans初始化是如何地方都是可能是中止的地方也就是要初始化為結束符了 46 int i,n; 47 ans[1][0]='1'; 48 ans[2][0]='1'; //由于左下標（二維陣列）是表示的是第幾個fabonacci數的，如何由于是第一個fabonacci是1，第二個也是 49 // 第二個也是1，并且他們都是個位的所以就初始化， 50 //（如果是第七個的化就是ans[7][0]=1,ans[7][1]=3,因為第7個fabonacci就是13了）只用初始化兩個足夠初始遞回就可以了 51 for(i=3;i<=1000;i++) 52 { 53 bigplus(ans[i-1],ans[i-2],i); //每次遞回都是得到一個第i個的值，由于ans是一個二維陣列，但是這里傳遞的其實是一維陣列的指標 54 //然后用bigplus函式里面的陣列a和b來接受的 55 } 56 int T; 57 scanf("%d",&T); 58 while(T--) 59 { 60 scanf("%d",&n); 61 printf("%s\n",ans[n]); 62 } 63 return 0; 64 } 65 66 */View Code
//相關的例題就是SCAUOJ里面的1143 多少個Fibonacci數
/************
1143 多少個Fibonacci數
時間限制:500MS 記憶體限制:65536K
提交次數:270 通過次數:16
題型: 編程題 語言: G++;GCC
Description
給你如下Fibonacci 數的定義：
F1 = 1
F2 = 2
Fn = Fn-1 + Fn-2 (n >= 3)
給你兩個數a與b，現要求你計算在a與b之間（包括a、b）有多少個Fibonacci 數
輸入格式
有多行，每行有兩個數a、b，使用空格分隔，a <= b <= 10^100（即最大10的100次方）
最后一行為兩個0
輸出格式
除了最后一行，其它每一行要求輸出在a與b之間的Fibonacci 數的個數，一行一個
輸入樣例
10 100
1234567890 9876543210
0 0
輸出樣例
5
4
************/
思路：這個題目和上面板子的不同其實就是給了一個范圍，很多人可能會想到這種用到范圍的都是用到莫隊排序的
但是我覺得這里好像不用的，如果您覺得可以用到的話歡迎給我留言，咱們一起探討一下呀哈哈（莫隊主要就是add函式和move函式，在對一維陣列的一些問題上面進行演算法1的
但是這里不用輸出值，而是要a到b中的fabonacci數有多少個的，其實就是和ab范圍內的比較，還是要吧fabonacci算出來的
就可以用到上面的板子了
先打一個前1000項的fb表（大數加法），然后 a，b在表中找位置（大數比較），那么他們之間的個數就是了
就是建表，然后比較，然后輸出個數即可
1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<string.h> 4 char ans[1010][1000]; //還是提醒一下吧為了優化空間的話這里吧ans二維數值是初始化為了cha型別的， 5 void bigplus(char a[],char b[],int t)//這個高精度計算的函式和上面的板子是一樣的沒有變化 6 { 7 int c[1000],d[1000]; 8 int n,m,i=1,j=1,k; 9 memset(c,0,sizeof(c)); 10 memset(d,0,sizeof(d)); 11 n=strlen(a); 12 m=strlen(b); 13 for(k=n-1;k>=0;k--) 14 c[i++]=a[k]-'0'; 15 for(k=m-1;k>=0;k--) 16 d[j++]=b[k]-'0'; 17 k=m>n?m:n; 18 for(int i=1;i<=k;i++) 19 { 20 c[i+1]+=(c[i]+d[i])/10; 21 c[i]=(c[i]+d[i])%10; 22 } 23 if(c[k+1])k+=1; 24 j=0; 25 for(i=k;i>=1;i--) 26 { 27 ans[t][j++]=c[i]+'0'; 28 } 29 } 30 /****之后就是要有一個高精度比較，肯定不可以直接用><來比較的，因為數值都被放在了數陣列里面了 31 除非就是用c++里面的多載運算子才可以用<和>進行比較了,所以就需要吧輸入的a和b這兩個邊界和我們已經制好的表（也就是那個ans二維陣列里面存放的值進行比較 32 這時候就要用到另外一個比較函式了我叫他bigcmp就是高精度比較，如果兩個東西經過bigcmp比較之后回傳的是1 33 表示前一個大于后一個，然后回傳的是-1表示的是兩個相等的，如果是回傳0的話就表示后一個大于前一個的 34 *****/ 35 //這個函式的思路肯定就是先比長度嘛，用strlen，長度長的自然就大，然后如果長度一樣的話再從高位一項一項的比下來哈哈 36 //感覺有點麻煩，不知大佬們有啥好的方法呢？ 37 38 int bigcmp(char a[],char b[]) 39 { 40 int i,n,m; 41 n=strlen(a); 42 m=strlen(b); 43 if(n>m)return 1; 44 else if(n<m)return 0; 45 46 //長度一樣的時候就從高位開始比，輸入的范圍和我們ans數值的存放的數其實高位就是從0開始的了， 47 // 所以在bigplus函式里面最后就是要吧c數值賦給ans的時候是要倒敘的， 48 // 使得這個數值的最高位是存放在ans數值的0位上的，也方便了bigcmp的比較了 49 else 50 { 51 for(i=0;i<n;i++) //因為這里n=m，所以以n或者m作為邊界都是可以的 52 { 53 if(a[i]>b[i])return 1; 54 else if(a[i]<b[i])return 0; 55 else //如果還是相等的話就繼續比較下面的數即可了 56 continue; 57 58 } 59 } 60 return -1; //如果直到最后都沒有比較出來的話說明這兩個數是相等的 61 } 62 int main() 63 { 64 int i,j; 65 char s1[1000],s2[1000]; //s1和s2陣列是用來存放我們要輸入的兩個數（就是左右范圍了） 66 memset(ans,'\0',sizeof(ans)); 67 ans[1][0]='1'; 68 ans[2][0]='2'; 69 for(i=3;i<=1000;i++) 70 bigplus(ans[i-1],ans[i-2],i);//注意：不要寫成了ans[1]和ans[2]作為第一二引數了(哈哈我剛開始就寫錯了） 71 while(scanf("%s %s",s1,s2)) 72 { 73 int cnt=0; //計算這個范圍里面有多少個fabonacci數 像這種計數器變數的話一般都是用sum或者是cnt是count的縮寫,用做計數器 74 75 if(!((s1[0]-'0')||(s2[0]-'0')))break;//就是只要不是兩個輸入的都是0的話都是可以進行下去的，如果都是0的話就break 76 for(i=1;i<=1000;i++) //回圈我們剛剛制成的fabonacci表（ans陣列） 77 { //再提醒一下回傳值，不然你肯定又翻上面看哈哈 78 //比較之后回傳的是1表示前一個大于后一個，然后回傳的是-1表示的是兩個相等的， 79 //如果是回傳0的話就表示后一個大于前一個 80 if(bigcmp(ans[i],s1)==-1) //兩個相等的話 81 { 82 cnt=1; //表示的是左范圍就是一個fabonacci數了，就提前的+1，然后i++就是下次就不用又比較一次了，只要出現了這個情況就break 83 i++; 84 break; 85 86 } 87 if(bigcmp(ans[i],s1)>0) //如果s1小的話 88 { 89 cnt=0; 90 break; 91 92 } 93 } //開始我差點也搞混了，就是for里面嵌套一個if，這個if里面有一個break的話就會直接跳出最近的那個for(別笑，我剛開始好真的傻了） 94 95 for(j=i;j<=1000;j++) //如果左邊界也是fabonacci的剛剛就把cnt設定為了1的，然后i++，就相當于已經把左邊界是fabanacci數記錄了，cnt=1了； 96 97 if(bigcmp(ans[j],s2)<=0)cnt++; 98 else 99 break; //用這個來結束 100 printf("%d\n",cnt); 101 } 102 return 0; 103 104 }View Code
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/61760.html
標籤：C