@ggg0820
禮拜二考了軟體實作的期中，考試是上機考，每25分鐘會公佈題目，需要在下一題公佈前寫好程式並得到答案。（意即如果寫出了巨大的遞迴，很可能會超出時間，沒有答案就沒有分數。） 總共考了6題，裡面題目有2題印象很深： 1. 把質數從小排到大，輸入正整數n，輸出第n個質數的值。例如輸入1，輸出2；輸入2，輸出3。 要求：當n=100,000時，必須於1秒內輸出結果，否則只算半對。 2.費氏數列第2^2022項以十進位表示的末三位（除以1000的餘數） 第一題沒有任何頭緒，第二題要把數列寫成非遞迴形式，但如果用一般式（黃金比例），浮點數運算會有誤差，所以要用矩陣對角化的概念去寫。 現在覺得數學爛連怎麼解題都沒有頭緒QQ
10 comments
第一題想好久不知道要怎麼一秒算出來(提高硬體等級?) 第二題不是拿到第2^2022項後，再取後面三位數就可以了嗎?
我發現1500一循環
問題在於第2^2022項如果用一般算法 算出來可能宇宙都毀滅了 而且二進位下這樣會佔用超級多記憶體
好吧我錯了
第一題大概要用埃拉托斯特尼篩法 第二題感覺好麻煩@@
第一題用那個篩法還是要注意怎麼算第幾個質數，還要注意語法把速度拉到最快 第二題比第一題還簡單 5行內結束
第一題建表(誤) 第二題的話直接加完取餘會花多久時間
第二題我來個pseudo code time complexity應該是1024288^2以內的加法… 事實上用excel就可以發現有break的關係整體運算量是1024288+1500^2 int f[]; int i,j; int search_finish=0; int loop_remainder; f[0]=f[1]=1; for (i=0;i<1024288;i++) f[i+2]=((f[i]+f[i+1])-1000)<0)? f[i]+f[i+1] : f[i]+f[i+1]-1000; int (i=0;i<1024288;i++) { for (j=1;j<i;J++) if( f[j]==f[i] )&& (f[j+1]==f[i+1]) ) { search_finish=1; break; } if(finish_finish) break; } loop_remainder= mod ( 1<<2022 - j, i); printf( %d, f[ j+i] );
已經更新解答了！ https://noise.cash/post/xg7k4n5tp66m 直接算的話要10^594天以上
我沒有要直接算啦，根據鴿籠原理最多1000001項就會有循環囉 然後再用Eular φ function算項數複雜度是nlogn的