算法講解之 一 題 多 解

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

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

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

4、燈是否開(kāi)著，如果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.（運(yùn)行次數(shù)：n ）,2,數(shù) 學(xué) 方 法（單層for循環(huán)）,算法二,算法講解,根據(jù)觀察我們發(fā)現(xiàn)，最后仍然亮著的都是自然數(shù)的平方數(shù)，所以可以得到一層運(yùn)算：for i:=1 to trunc(sqrt(n)) do write(i*i,’ ‘);,程序（moni_2.pas）,var n,