主题:[讨论]【求救】关于有限范围内合数排列的问题
桃花源居民
[专家分:0] 发布于 2007-07-10 16:31:00
把小于N的所有合数重新排列,使每对相邻的数都有大于或等于2的公约数
【例】
输入:
10
输出:
4 8 6 9 (输入输出均在屏幕上)
希望各位高手给出示例代码,如果时间仓促,描述以下算法或写出伪代码也可,菜鸟在此谢过!!![em2]
回复列表 (共3个回复)
沙发
Matodied [专家分:7560] 发布于 2007-07-10 21:28:00
算法:
(1)把小于N的合数全部存到数组里。
(2)用递归来实现:
[1]:p(i)过程表示取第i个合数。
[2]:当每取一个合数时,判断这个合数与前一个合数是不是互质,(可以专门设一个函数,判断两个数是否互质),是就重取,否则取下一个合数,i+1。
[3]:当取到最后一个时,输出,结束。
板凳
桃花源居民 [专家分:0] 发布于 2007-07-12 17:04:00
求你们了,帮帮我,怎么就一个人回答呀!5555555555~~~~~~
3 楼
Matodied [专家分:7560] 发布于 2007-07-12 21:29:00
还有前面一个帖子怎么不打分?
花了这么长时间总算做出来了……
TYPE
arr = ARRAY[1..2000] OF INTEGER;
VAR
a, s: arr; t: INTEGER;
PROCEDURE pri;
VAR
i: INTEGER;
BEGIN
FOR i:=1 TO t DO WRITE(s[i], ' ');
HALT;
END;
FUNCTION gcd(x, y: INTEGER): INTEGER;
VAR
z: INTEGER;
BEGIN
z := x MOD y;
IF z = 0 THEN gcd := y ELSE gcd := gcd(y, z);
END;
PROCEDURE try(i: INTEGER);
VAR
j, k: INTEGER; f: BOOLEAN;
BEGIN
FOR j:=1 TO t DO BEGIN
s[i] := a[j];
IF i > 1 THEN BEGIN
IF (gcd(s[i], s[i - 1]) = 1) THEN f := FALSE ELSE f := TRUE;
FOR k:=1 TO i - 1 DO BEGIN
IF s[i] = s[k] THEN f := FALSE;
END;
END ELSE BEGIN
f := TRUE;
END;
IF f THEN BEGIN
IF i < t THEN try(i + 1) ELSE pri;
END;
END;
END;
PROCEDURE work_out(p: INTEGER);
VAR
i, j, sum: INTEGER; f: BOOLEAN;
BEGIN
sum := 0;
FOR i:=4 TO p - 1 DO BEGIN
f := FALSE;
FOR j:=2 TO TRUNC(SQRT(i)) DO BEGIN
IF i MOD j = 0 THEN f := TRUE;
END;
IF f THEN BEGIN
sum := sum + 1; a[sum] := i;
END;
END;
t := sum
END;
VAR
k: INTEGER;
BEGIN
READLN(k);
t := 0;
work_out(k);
try(1);
END.
也要加分。
我来回复