Diễn đàn tin học Nguyễn Văn Linh

The second house for every one
 
IndexTrợ giúpTìm kiếmThành viênĐăng kýĐăng Nhập

Share | 
 

 Vòng tròn nguyên tố

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giảThông điệp
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Vòng tròn nguyên tố   Sat 20 Mar 2010, 19:24

Có một vòng tròn lớn, trên đó có 2n vòng tròn nhỏ, mỗi vòng tròn được đánh số từ 1 đến 2n theo chiều kim đồng hồ, số 1 ở trên cùng. Hãy điền các số từ 1..2n vào các ô tròn trên sao cho tổng hai ô tròn liên tiếp bất kì là số nguyên tố.
Về Đầu Trang Go down
toan_9a2
Gà con


Tổng số bài gửi : 17
Join date : 03/05/2010

Bài gửiTiêu đề: Re: Vòng tròn nguyên tố   Mon 03 May 2010, 20:37

bài này dùng đẹ quy quay lui............................
Về Đầu Trang Go down
hoangtin14
Mèo con


Tổng số bài gửi : 96
Join date : 08/02/2010
Age : 21
Đến từ : Bình Định

Bài gửiTiêu đề: Re: Vòng tròn nguyên tố   Sun 09 May 2010, 07:01

Thì post code lên cho anh em coi thử coi.
Về Đầu Trang Go down
toan_9a2
Gà con


Tổng số bài gửi : 17
Join date : 03/05/2010

Bài gửiTiêu đề: Re: Vòng tròn nguyên tố   Sun 09 May 2010, 13:40

Code:
var  x:array[1..10000] of int64;
    n,k,t,d:int64;
    i:longint;

function      kt(t:integer):boolean;
var i:longint;
begin
  i:=2;
  while ((t mod i) <>0) and (i<= sqrt(t)) do
  i:=i+1;
  if ((i>sqrt(t)) and (t>1)) then kt:=true else kt:=false;
  end;
procedure  result;
var h:longint;
begin
  inc(h);
  for i:=1 to 2*n  do write(x[i]);
  writeln;
  if h>10000 then exit;
end;
function  trung(i,j:integer):boolean;
var k:longint;
begin
  trung:=false;
  for k:=1 to i-1 do
  if x[k]=j then trung:=true;
end;
procedure    tang;
begin
    inc(d);
end;
procedure    try(i:integer);
var d:int64;
    j:longint;
begin

  x[1]:=1;
  for j:=2 to 2*n do
  if( not trung(i,j) and (kt(x[i-1]+j)=true)) then
    begin
      x[i]:=j;
      if ((i=2*n) and (kt(x[1]+x[2*n])=true)) then result  else try(i+1);
    end;
      end;
procedure    sinh(i:integer);
var j:longint;
begin

  x[1]:=1;
  for j:=2 to 2*n do
  if( not trung(i,j) and (kt(x[i-1]+j)=true)) then
    begin
      x[i]:=j;
      if ((i=2*n) and (kt(x[1]+x[2*n])=true)) then tang  else sinh(i+1);
    end;
      end;
BEGIN
  readln(n);
  sinh(2);
  writeln(d);
  try(2);
  readln
END.
Về Đầu Trang Go down
toan_9a2
Gà con


Tổng số bài gửi : 17
Join date : 03/05/2010

Bài gửiTiêu đề: Re: Vòng tròn nguyên tố   Sun 09 May 2010, 13:42

vì bài này mình đưa ra cả số cách có thể điền dc nên chạy n=10 hơi lâu. có ai có cách nào
chỉ cần 1 lần try mà ghi dc cả số cách điền lẫn thứ thự điền thì send lên nhé> Smile
Về Đầu Trang Go down
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Vòng tròn nguyên tố   Tue 11 May 2010, 18:33

Bạn toan_9a2 có phong cách code trông cũng khá chuyên nghiệp đấy ^^. Mà chắc có lẽ bạn chuộng FP hơn đúng ko. Về cái dữ liệu thì cũng ko cần đến int64 đâu
Về Đầu Trang Go down
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Vòng tròn nguyên tố   Tue 11 May 2010, 19:08

Có vẻ toan_9a2 thích bài này ấy nhỉ. Về code của bạn, mình có 4 góp ý nhỏ.

Thứ nhất là ta có thể dùng một mảng kiểu boolean để đánh dấu các số đã chọn rồi, như vậy khi kiểm tra sẽ tiết kiệm rất nhiều thời gian. (dùng mảng này để thay thế ham "trung" của bạn)

Thứ hai bạn dùng hơi nhiều chương trình con. Tất nhiên là chương trình sẽ rành mạch, tuy nhiên bạn để ý xem, ví dụ thủ tục "tang" chỉ có đúng 1 câu lệnh. Như vậy là vừa làm code bị dài ko cần thiết, vừa tốn thời gian .Vì nếu đem luôn 1 câu lệnh ấy vô thì mất 1 đơn vị thời gian, nhưng nếu dùng thủ tục như vậy sẽ tốn thời gian nhiều hơn rất nhiều, vì tốn thời gian chương trình tìm đến thủ tục, mở thủ tục, thực hiện câu lệnh, đóng thủ tục. Đó là chưa kể đến chương trình còn phải huy động bộ nhớ cho mỗi lần vào một hàm hoặc thủ tục, kiểm tra tham số, lưu trữ và cách li các biễn cục bộ ra khỏi các biễn có "phạm vi bao hàm" cùng tên,...

Thứ ba, thật ra bạn dùng FP-tốc độ cao hơn TP (tụi mình hay dùng TP hơn ^^) nên bạn bảo với n=10 thì chạy hơi lâu chứ nếu chạy trong TP thì là rất lâu chứ ko phải hơi lâu đâu. Tuy nhiên bài của bạn thì rất tốt rồi, mình thì cũng làm tương tự thôi. Tuy nhiên với góp ý thứ nhất và thứ hai thì có thể giúp chương trình chạy nhanh hơn đấy.^^

Thứ tư, nếu trong đời sống thì ta hay muốn xem kết quả kiểu số cấu hình rồi mới đến từng cấu hình. Tuy nhiên trong tin học, ta lại hay ngược lại hơn. Bởi vì làm thế sẽ lợi hơn. Cái này chắc bạn cũng hiểu. Vì vậy bạn làm như thế là chạy đến 2 lần ->phí. Nhưng nói thế chứ vẫn có bài ta sẽ thông báo số cấu hình trước trước hoặc thông báo số cấu hình đến 2 lần, ở đầu và cuối (tùy thôi, đó chỉ là cách trình bày^^). Đó là các bài có cách tính số cấu hình riêng, như bài tháp hà nội chẳng hạn.
Về Đầu Trang Go down
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Vòng tròn nguyên tố   Tue 11 May 2010, 19:57

Đây là code của mình. Mình ghi ra file cho nhanh.
Code:
program vong_tron_nguyen_to;
uses crt;
const max=100; fi='vtnt.txt';
var a:array[1..max] of integer;
    kt:array[1..max] of boolean;
    i,n,dem,l:integer; f:text;

procedure nhap;
 begin
  clrscr;
  write('nhap n: ');readln(n);
 end;

function ktnt(k:integer):boolean;
 begin
  ktnt:=false;
  if k<2 then exit;
  for l:=2 to trunc(sqrt(k)) do
  if k mod l=0 then exit;
  ktnt:=true;
 end;

procedure try(i:integer);
 var j:integer;
 begin
  for j:=2 to 2*n do
  if (kt[j])and(ktnt(a[i-1]+j)) then
    begin
    a[i]:=j;kt[j]:=false;
    if (i=2*n)and(ktnt(a[1]+a[2*n])) then
      begin
      inc(dem);
      for l:=1 to 2*n do write(f,a[l],' ');
      writeln(f);
      end
    else try(i+1);
    kt[j]:=true;
    end;
 end;

procedure tinh;
 begin
  a[1]:=1; dem:=0;
  for i:=2 to 2*n do kt[i]:=true;
  assign(f,fi);
  rewrite(f);
  try(2);
  writeln(f,'Co tat ca ',dem,' cach.');
  close(f);
 end;

begin
 nhap;
 tinh;
end.

Thật ra bài này chỉ yêu cầu ghi ra 1 cấu hình thôi. Nhưng mình làm theo bạn luôn.


Bài này nếu biến đổi yêu cầu lại thành cho biết số cấu hình thì sẽ thú vị hơn.
Về Đầu Trang Go down
toan_9a2
Gà con


Tổng số bài gửi : 17
Join date : 03/05/2010

Bài gửiTiêu đề: Re: Vòng tròn nguyên tố   Tue 11 May 2010, 20:50

uh.cam on cau da gop y.
tuy nhien nếu đề bài yêu cầu ghi số cách trc thì làm sao zậy.
Về Đầu Trang Go down
toan_9a2
Gà con


Tổng số bài gửi : 17
Join date : 03/05/2010

Bài gửiTiêu đề: Re: Vòng tròn nguyên tố   Tue 11 May 2010, 20:57

cho mình xin yahho dc không
Về Đầu Trang Go down
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Vòng tròn nguyên tố   Thu 13 May 2010, 07:37

Uhm, được thôi. Bạn nhìn thông báo tại trang chủ ý. Mà mình đôi khi ít lên lắm. ^^

Sao bạn ko làm một vài bài khác nhỉ.
Về Đầu Trang Go down
hcungphuc
Gà con


Tổng số bài gửi : 11
Join date : 13/05/2010

Bài gửiTiêu đề: Re: Vòng tròn nguyên tố   Thu 13 May 2010, 08:40

toan_9a2 đã viết:
uh.cam on cau da gop y.
tuy nhien nếu đề bài yêu cầu ghi số cách trc thì làm sao zậy.

laughing Rất đơn giản. Nếu ghi ra file thì ta sẽ ghi cấu hình trước, từ dòng 2 trở xuống, sau khi có số cấu hình thì lên lại dòng 1 ghi ra. Mà chắc ko đến nỗi bắt bẻ vậy đâu, chẳng qua là trình bày thôi mà.
Về Đầu Trang Go down
tnmnhatminh
Gà mờ


Tổng số bài gửi : 2
Join date : 13/05/2010

Bài gửiTiêu đề: Re: Vòng tròn nguyên tố   Thu 13 May 2010, 08:53

Đáng lẽ chỉ cần ghi ra 1 kết quả thôi chứ nhỉ. Tớ nhớ hồi cô dạy tớ làm thế, chạy được n=50
Về Đầu Trang Go down
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Vòng tròn nguyên tố   Thu 13 May 2010, 09:02

Cả hai bạn đều nói đúng cả ^^
Về Đầu Trang Go down
Hovanthong
Admin
Admin


Tổng số bài gửi : 101
Join date : 25/07/2010
Age : 22
Đến từ : Hưng nguyên-Nghệ An

Bài gửiTiêu đề: Re: Vòng tròn nguyên tố   Mon 26 Jul 2010, 22:56

Code:

Var
        n:longint;
        count:qword;
        a:array[0..20]of longint;
        kq:array[0..10000,0..100]of longint;
        DaXet,NT:array[0..100]of boolean;
        Function Test(k:longint):boolean;
        Var
                i:longint;
        Begin
        Test:=true;
        If (k=2)or(k=3) then
                exit(true)
        Else
                For i:=2 to trunc(sqrt(k)) do
                        If k mod i=0 then
                                exit(false);
        End;
        Procedure Init;
        Var
                i:longint;
        Begin
        Readln(n);
        a[1]:=1;
        a[2*n+1]:=1;
        For i:=1 to 39 do
                Nt[i]:=Test(i);
        End;
        Procedure Update;
        Begin
        inc(count);
        If count<=10000 then
                kq[count]:=a;
        End;
        Procedure Try(k:longint);
        Var
                i:longint;
        Begin
        If k=2*n+1 then
                If NT[a[k]+a[k-1]] then
                        begin
                        Update;
                        exit;
                        end;
        For i:=2 to 2*n do
                If not DaXet[i] then
                        begin
                        a[k]:=i;
                        DaXet[i]:=true;
                        If NT[a[k-1]+a[k]] then
                                Try(k+1);
                        DaXet[i]:=false;
                        end;
        End;
        Procedure Print;
        Var
                i,j:longint;
        Begin
        Writeln(count);
        If count>10000 then
                count:=10000;
        For i:=1 to count do
                begin
                For j:=1 to 2*n do
                        write(kq[i,j],' ');
                end;
        End;
        Procedure Solve;
        Begin
        Init;
        Try(2);
        Print;
        End;
BEGIN
Solve;
END.







Về Đầu Trang Go down
http://thongtra.forum-viet.com
Sponsored content




Bài gửiTiêu đề: Re: Vòng tròn nguyên tố   Today at 18:50

Về Đầu Trang Go down
 
Vòng tròn nguyên tố
Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 
Trang 1 trong tổng số 1 trang
 Similar topics
-
» Rừng Mắm - Bình Nguyên Lộc
» Nguyên liệu và dụng cụ đan len
» Những Giai Thoại về Các Vị Tam Nguyên
» THƠ PHƯƠNG NGUYÊN
» Gánh cải Trạng Nguyên

Permissions in this forum:Bạn không có quyền trả lời bài viết
Diễn đàn tin học Nguyễn Văn Linh :: Góc tin học :: Lớp chuyên tin-
Chuyển đến