cần giúp bài "dãy số hạnh phúc"

**okmen910** · 31-12-2007 14:35

Dãy số tự nhiên A(1),A(2),...A(k)được gọi là dãy số hạnh phúc khi:
+Dãy trên là một dãy giảm dần
+Với mọi i,A(i) hoặc là số nguyên tố hoặc phải là ước một trong các số A(1);A(2);...;A(i-1)
ví dụ:8,7,5,4,3,2,1 là dãy số hạnh phúc (với N=8, dãy số hạnh phúc có 7 phần tử).
Yêu cầu:Nhập một số tự nhiên N từ bàn phím và in ra màn hình một dãy hạnh phúc càng dài càng tốt với số hạng đầu tiên là N

Cảm ơn các bác!!!

**m2mpro** · 31-12-2007 16:32

Bài này hóc búa đấy, đợi tí đang suy nghĩ... có lẽ dùng hai hàm check và dùng mảng gán là được

**m2mpro** · 31-12-2007 16:57

Code:

Program baitap;
uses crt;
type
   mang = array[1..100] of integer;
var
   a,x:mang;
   n,i,k:integer;
Function ngto(a:mang;i:integer):boolean;
var k:integer;
begin
   ngto:=false;
   if a[i]<2 then exit;
   FOr k:=2 to round(sqrt(a[i])) do
       If a[i] mod k = 0 then exit;
   ngto:=true;
end;
Function uocso(a:mang;i,n:integer):boolean;
var k:integer;
begin
   For k:=n downto i+1 do
   If a[k] mod a[i] = 0 then 
   begin
      uocso:=true;
      exit;
   end
   else uocso:=false;
end;
BEGIN
Write('n = ');
Readln(n);
For i:=n downto 1 do
  a[i]:=i;
i:=1;
k:=1;
While i<=n do
begin
  IF ngto(a,i) or uocso(a,i,n) then
  begin
     x[k]:=a[i];
     k:=k+1;
     i:=i+1;
  end else
     i:=i+1;
end;
For i:=k downto 1 do
write(x[i]);
Readln;
END.

Test luôn rồi đấy. THuật toán hơi rắc rối:
Đầu tiên gán từ n về 1 cho mảng a rồi là kiểm tra xem a[i] có phải số nguyên tố và ước số không. Nếu là ước số và nguyên tố thì gán vào mảng x. CHúc bạn học tốt.

**phuclun** · 31-12-2007 17:19

sao tui ko hiểu bài bạn nhỉ,tui giống bạn phần kt SNT nhưng mấy phần khác tui ko hiểu lắm.Thuật toán tui cũng giống bạn nhưng tui nghĩ chỉ cần làm như thế này

Code:

 
k:=2;
for i:=n downto 1 do
     if (ngt(i)=true) or (n mod i=0) then
         begin
             a[k]:=i
             inc(k);
         end;

Chỉ vậy thôi,vì nó là ước của các số khác thì nó cũng là ước cuả n,chỉ cần xem n có chia hết cho nó ko thôi.
Còn về phần kt số nguyên tố thì chắc dùng 1 tham số i là đc rồi bạn ạ,ko cần dùng tham số a đâu.Tôi chắc chắn bài bạn sẽ báo trùng tham số bởi vì bạn thông báo tham số a dạng mảng là biến toàn cục mà bạn còn thông báo thêm ở các thủ tục nưã.Chắc trong quá trình code bài lên đây bạn viết thưà.
Chúc bạn vui vẻ

**m2mpro** · 31-12-2007 18:39

Code:

Chỉ vậy thôi,vì nó là ước của các số khác thì nó cũng là ước cuả n,chỉ cần xem n có chia hết cho nó ko thôi.

Ừ, không nghĩ ra.. đúng là chỉ cần thế. Tại đọc cái đề không rõ ở chỗ "Với mọi i,A(i) hoặc là số nguyên tố hoặc phải là ước một trong các số A(1);A(2);...;A(i-1)" nên lầm lẫn.Còn bài của tui thì tại dùng mảng để lưu giá trị nên mới dùng tham số a:mang. Cám ơn bạn đã góp ý.

**okmen910** · 09-01-2008 16:15

em không hiểu lắm chỗ số nguyên tố.Các bác có thể giải thích thêm được không

**gianhut** · 10-01-2008 05:38

Function ngto(a:mang;i:integer):boolean;
var k:integer;
begin
ngto:=false;
if a[i]<2 then exit;
FOr k:=2 to round(sqrt(a[i])) do
If a[i] mod k = 0 then exit;
ngto:=true;
end;

nên làm thế này:

Code:

Function ngto(a:mang;i:integer):boolean;
var k:integer, loopEnd: integer;   
begin
   ngto:=false;
   if a[i]<2 then exit;
   loopEnd := round(sqrt(a[i]));
   FOr k:=2 to loopEnd do
       If a[i] mod k = 0 then exit;
   ngto:=true;
end;

như vậy thì sẽ ko cần phải tính lại round(sqrt(a[i])) mỗi lần chạy xong 1 vòng for. :-)
và tương tự cho các phần sau.

P.S.: thuật toán khá là tối ưu