Download presentation
Presentation is loading. Please wait.
1
综合实践之解题报告 七（一）班 陈贝希
2
模拟开关 【问题描述】有n盏灯排成一排，依次标号1，2，…，n，每盏灯都有一根拉线开关，最初电灯都是关 着的．现有n个人，都沿着电灯路线走过，第一个人走过时，把凡是号码是1的倍数的灯的开关拉一下； 接着第二个人走过时，把凡是号码是2的倍数的灯的开关拉一下；第三个走过时，把凡是号码是3的倍 数的灯的开关拉一下；…；最后，第n个人走过时，把最后那盏灯的开关拉一下．问最后都有哪些灯是 开着的？ 【输入文件】文件名：moni.in 文件中只有一行，包含一个整数（其中5≤n≤10000） 【输出文件】文件名：moni.out 文件共一行，分别为哪些开着灯的编号，如果没有灯开着，就输出0. 【样例输入】 10 【样例输出】 1 4 9
3
在道题十分明显，显然属于模拟算法 因为第一个人把号码是1的倍数的灯的开关拉一下；接 着第二个人把号码是2的倍数的灯的开关拉一下；第三 个人把号码是3的倍数的灯的开关拉一下 …so…
4
var a:array[ ] of boolean; n,i,j:longint; f:boolean; begin assign(input,'moni.in'); assign(output,'moni.out'); reset(input); rewrite(output); read(n); for i:=1 to n do for j:=1 to n div i do a[j*i]:=not(a[j*i]); if a[i] then write(i,' '); f:=true; end; if f=false then write('0'); close(input); close(output); end.
![var a:array[ ] of boolean; n,i,j:longint; f:boolean; begin. assign(input, moni.in ); assign(output, moni.out );](http://slidesplayer.com/slide/17375625/101/images/4/var+a%3Aarray%5B+%5D+of+boolean%3B+n%2Ci%2Cj%3Alongint%3B+f%3Aboolean%3B+begin.+assign%28input%2C+moni.in+%29%3B+assign%28output%2C+moni.out+%29%3B.jpg "reset(input); rewrite(output); read(n); for i:=1 to n do. for j:=1 to n div i do. a[j*i]:=not(a[j*i]); if a[i] then. write(i, ); f:=true; end; if f=false then write( 0 ); close(input); close(output); end.")
5
but 5≤n≤10000 依题意 o(n2) 大概需要运行100002 既108 运算量十分大，显然做法不好
6
假如有4盏灯，则 0.FFFF 1.TTTT 2.TFTF 3.TFFF 4.TFFT 第一盏和第四盏是亮的，为什么呢？
7
因为第i盏灯的开关次数受约数限制 eg.第六盏灯被第一个人，第二个人，第三个人，第六 个人开关过 一共更改四次，即6有4个约数：1，2，3，6 因为4是偶数，所以灯还是关的 要使灯是亮的，则要使约数个数为奇数
8
只有完全平方数约数的个数才是奇数 故四盏灯时，只有第一盏和第四盏是亮的
9
var n,i:longint; begin assign(input,'moni.in'); assign(output,'moni.out'); reset(input); rewrite(output); read(n); for i:=1 to trunc(sqrt(n)) do write(i*i,' '); if trunc(sqrt(n))=0 then write(0); close(input); close(output); end.
Similar presentations
