演算法設計

Question

要如何設計一個演算法來產生只可以被5及7整除的數列5,7,25,35,49,125,175,245,343,..........,M , M≦10的9次方??

數學符號顯示不出來.......

應該是
M小於等於10的9次方?? 才對

Answer 1

這題的觀念是DP (Dynamic Programming)
要由小到大產生只能被5以及7整除的數字 (<= 10^9)
前兩個數字是5和7沒問題
第三個數字呢?
(想法: 第三個數字一定是前面兩個數字乘以5或是7得到的)

雖然是DP，但是確切的觀念沒辦法三言兩語清楚
程式大概長下面這樣:

int f_num = s_num = 1;
int f_num_ptr = s_num_ptr = 0;
for (i = 1; ; i++)
{
num[i] = MIN(5 * f_num, 7 * s_num);
if (num[i] % 5 == 0)
f_num = num[++f_num_ptr];
if (num[i] % 7 == 0)
s_num = num[++s_num_ptr];
if (num[i] <= 1000000000)
printf("(%d): %d\n", i, num[i]);
else
break;
}

有興趣可以trace一下程式碼，會有比較深的體認
基本想法就是上面說的
大數字的解，是比較小的解*5或是*7得來的
小於等於10^9，這樣的數字總共有79個:
(1): 5
(2): 7
(3): 25
(4): 35
(5): 49
(6): 125
(7): 175
(8): 245
(9): 343
(10): 625
(11): 875
(12): 1225
(13): 1715
(14): 2401
(15): 3125
(16): 4375
(17): 6125
(18): 8575
(19): 12005
(20): 15625
(21): 16807
(22): 21875
(23): 30625
(24): 42875
(25): 60025
(26): 78125
(27): 84035
(28): 109375
(29): 117649
(30): 153125
(31): 214375
(32): 300125
(33): 390625
(34): 420175
(35): 546875
(36): 588245
(37): 765625
(38): 823543
(39): 1071875
(40): 1500625
(41): 1953125
(42): 2100875
(43): 2734375
(44): 2941225
(45): 3828125
(46): 4117715
(47): 5359375
(48): 5764801
(49): 7503125
(50): 9765625
(51): 10504375
(52): 13671875
(53): 14706125
(54): 19140625
(55): 20588575
(56): 26796875
(57): 28824005
(58): 37515625
(59): 40353607
(60): 48828125
(61): 52521875
(62): 68359375
(63): 73530625
(64): 95703125
(65): 102942875
(66): 133984375
(67): 144120025
(68): 187578125
(69): 201768035
(70): 244140625
(71): 262609375
(72): 282475249
(73): 341796875
(74): 367653125
(75): 478515625
(76): 514714375
(77): 669921875
(78): 720600125
(79): 937890625

2007-01-26 01:09:59 補充：
第一個回答的是不對的
例如20雖然可以被5整除，但是也會被2整除
不符合題目"只能被5和7整除"的條件

Answer 2

不明白你的意思，什麽是 M≦ 10的9次方??

至於產生可以被5及7整除的數列的演算法如下∶

START
FOR i = 1 to n STEP 1
IF i%5 = 0 OR i%7 = 0 THEN
PRINT i
END IF
NEXT
END

其中 n 為取值範圍（上限）

有問題再討論。