算法講解之 一 題 多 解

1、,算法講解之一 題 多 解,模擬開關(guān)FPC程序編寫,模擬開關(guān),【問題描述】 有n盞燈排成一排，依次標(biāo)號1，2，…，n，每盞燈都有一根拉線開關(guān)，最初電燈都是關(guān)著的．現(xiàn)有n個人，都沿著電燈路線走過，第一個人走過時，把凡是號碼是1的倍數(shù)的燈的開關(guān)拉一下；接著第二個人走過時，把凡是號碼是2的倍數(shù)的燈的開關(guān)拉一下；第三個走過時，把凡是號碼是3的倍數(shù)的燈的開關(guān)拉一下；……；最后，第n個人走過時，把最后那盞燈的開關(guān)拉一下

2、．問最后都有哪些燈是開著的？【輸入文件】文件名：moni.in 文件中只有一行，包含一個整數(shù)（其中5≤n≤10000）【輸出文件】文件名：moni.out 文件共一行，分別為哪些開著燈的編號?！緲永斎搿?10【樣例輸出】 1 4 9,模 擬 運 行（雙層for循環(huán)）,算法一,算法講解,為了判斷燈的開關(guān)，我們需要標(biāo)志性數(shù)組：

3、b:array[1..10000]of longint;根據(jù)題目我們知道，拉開關(guān)的規(guī)律就是依次把1的倍數(shù)、2的倍數(shù)直到n的倍數(shù)的開關(guān)拉一下，那么我們就可以得到第一次for循環(huán)：for i:=1 to n do因為每次所有燈都要判斷，所以第二層for循環(huán)就是：for j:=1 to n do當(dāng)?shù)趈盞燈是i的倍數(shù)時，就將b[j]置為相反的值：If j mod i=0 then b[j]:=not b[j];最后用for循環(huán)判斷

4、燈是否開著，如果b[j]仍為原值則輸出：for i:=1 to n do if not b[j] then write(j,’ ‘);,程序（moni_1.pas）,var n,i,j:longint; a:array[1..10000]of boolean;begin read(n); for i:=1 to n do for j:=1 to n do if j mod i=0 then a[j]:=

5、not a[j]; for i:=1 to n do if a[i] then write(i,' ');end.（運行次數(shù)：n ）,2,數(shù) 學(xué) 方 法（單層for循環(huán)）,算法二,算法講解,根據(jù)觀察我們發(fā)現(xiàn)，最后仍然亮著的都是自然數(shù)的平方數(shù)，所以可以得到一層運算：for i:=1 to trunc(sqrt(n)) do write(i*i,’ ‘);,程序（moni_2.pas）,var n,