[isteam test 2011] k4,5,6

[07520004]

Anh nói đúng ý em đó. Nhưng nếu nói sai hay chưa tối ưu thì phải cho thử vd test, để chứng minh chứ.

Bạn đó làm rồi, đã nói được là giải thuật kia sẽ sai khi input một số có thể được phân tích thành tổng của n số hạng nguyên tố với n khác 2 và n khác 3.

Người ta chứng minh giải thuật là đúng. Nếu không chứng minh được trường hợp tổng quát thì phải chứng minh được khoảng giá trị của input mà giải thuật sẽ đúng. Đừng có cố đẩy cái khó của mình cho người khác chứ

[07520004]

thì bạn Hoàng đã làm hết sức rồi, nếu bạn nào có cách đúng thì cứ đưa ra = code cụ thế.

Sai là sai. Việc không ai giải tốt hơn không khiến em bỗng dưng trở nên đúng. Việc nào ra việc đó, làm việc một cách khoa học chứ.

[11520673]

thì bạn Hoàng đã làm hết sức rồi, nếu bạn nào có cách đúng thì cứ đưa ra = code cụ thế.

đây là topic để tranh luận mà! Hix nếu đã biết cách đúng nhất luôn thì đâu cần tranh luận làm gì! Đag muốn học hỏi và tìm ra cách hay nhất nè!

[11520118]

Mình có ý kiến bài của bạn đây.giả thuyết Golback Euler( nguồn: http://vi.wikipedia.org/wiki/Số_nguyên_tố):

Năm 1742, nhà toán học Đức Goldbach viết thư cho Euler biết rằng ông mạo hiểm đưa ra bài toán: Mọi số tự nhiên lớn hơn 5 đều biểu diễn được dưới dạng tổng của 3 số nguyên tố. Euler trả lời rằng theo ông, mọi số chẵn lớn hơn 2 đều biểu diễn được dưới dạng tổng của 2 số nguyên tố. Nếu chứng minh được một trong hai mệnh đề thì sẽ chứng minh được mệnh đề còn lại. 200 năm sau, đến năm 1937, nhà toán học Liên Xô Vinogradov đã giải quyết gần trọn vẹn bài toán đó bằng cách chứng minh rằng mọi số lẻ đủ lớn đều có thể biểu diễn được dưới dạng tổng của 3 số nguyên tố.
Cho đến nay, bài toán Goldbach-Euler vẫn chưa giải được hoàn toàn. Nếu mệnh đề của Euler là đúng, hãy chứng minh mệnh đề Goldbach. Giải: Cho số tự nhiên n>5, ta sẽ chứng minh rằng n viết được dưới dạng tổng của 3 số nguyên tố --> nghĩa là muốn chứng minh cả 2, phải giả sử 1 trog 2 cái đúng !!???

Về cách của bạn, chỉ tìm tổ hợp có 2 và 3 phần tử! Vậy thì có thể có 1 số nào đó ko tồn tại tổ hợp 2,3 phần tử mà bạn ko biết thì sao?? Cái thứ 2, mình bổ sung thêm cách của bạn để chạy nhanh hơn. Là khi xét truong hop 2 to hop xong, nếu tồn tại, hãy break để chtrình dừng luôn khỏi tìm tổ hợp 3 phần tử. Bảo đảm chạy nhanh hơn!

Cách này ban đầu mình cũg nghĩ tới r, nhưng mình tìm ra đc cách tổng quát hơn cho bài này. Hix nhưng vẫn ko thể tối ưu hóa bài này đc. vì cách của mình là tìm tất cả các tổ hợp r lọc tất cả để chọn tổ hợp phần tử ngắn nhất. Có điều làm vậy thì dung lượng mảng bộ nhớ lại ko cho phép. Quả thật làm mình rất băn khoăn, nên chọn pp như bạn hay làm theo tổng quát như mình, vì rõ ràng làm tổng quát mình chỉ chạy đến 600 là tràn mảng.Em rất muốn xin ý kiến của các anh chị thầy cô về chuyện này!

Ý bạn cũng đúng, còn về phần tối ưu mình đã suy nghĩ đây, nếu kiểu lặp đó mà bạn break ra như thế thì sẽ thiếu trường hợp (chắc luôn), mình thấy sau khi tìm xong thì sẽ có những cách chỉ đổi chỗ vị trí số cho nhau: vd 46= 43+3 nhưng nếu lặp thế nó sẽ thành 46=43+3 và 46=3+43,....

[11520673]

Bạn Hoàng làm ko gọi là sai! Vấn đề ở đây là giải thuật làm! Mình đag băn khoăn, ko biết khi làm bài ta nên làm theo kiểu chaỵ for xét thử 2 phần tử, r 3 phần tử thôi hay làm tổng quát hết là đúng. Bạn có đag theo dõi mấy bài viết trên ko vậy?? Mà hình như bạn cũg ko hiểu bạn Hoàng đag làm theo cách gì thì phải???

[07520004]

Thì em có nói sai thành đúng gì đâu. Em nghĩ đã có người tìm được chỗ sai, sao k tiện thể chỉnh nó lại luôn đi rồi post code đúng lên thay vì tranh luận quá nhiều.

Nếu em cũng đồng ý nó sai thì em ngồi yên đi cho người khác tranh luận, rõ ràng các post trước của em chỉ nhằm chỉ trích người đã chỉ ra điểm sai chứ không có ý xây dựng. Em bảo người ta quá lời rồi còn nghi ngờ trình độ người viết, chính kiểu post đó mới làm phát sinh quá nhiều tranh luận không cần thiết đó. Bây giờ đồng ý là sai đúng không, vậy thì ngồi yên đi nhá, chờ tác giả giải thuật trả lời.

[11520673]

Ý bạn cũng đúng, còn về phần tối ưu mình đã suy nghĩ đây, nếu kiểu lặp đó mà bạn break ra như thế thì sẽ thiếu trường hợp (chắc luôn), mình thấy sau khi tìm xong thì sẽ có những cách chỉ đổi chỗ vị trí số cho nhau: vd 46= 43+3 nhưng nếu lặp thế nó sẽ thành 46=43+3 và 46=3+43,....

lạ nhỉ! giả sử bạn ko break thì nó cũng ra vậy đúng ko? Hix mình ko hiểu C nên chỉ nhìn thấy bạn chạy for r đoán giải thuật bạn làm chứ cũg ko biết bạn có thêm gì ko? Vậy code bạn ra có bị trùng ko?

[07520004]

lạ nhỉ! giả sử bạn ko break thì nó cũng ra vậy đúng ko? Hix mình ko hiểu C nên chỉ nhìn thấy bạn chạy for r đoán cách bạn làm chứ cũg ko biết bạn có thêm gì ko? Vậy code bạn ra có bị trùng ko?

11520118 nó không xuất kq ra màn hình ngay mà thêm loại kết quả trùng rồi mới xuất. Tận dụng khả năng hỗ trợ các CTDL cấp cao của python.

PS: Nói vậy đúng không em, anh chưa coi kỹ đó =))

[11520118]

11520118 nó không xuất kq ra màn hình ngay mà thêm loại kết quả trùng rồi mới xuất. Tận dụng khả năng hỗ trợ các CTDL cấp cao của python.

PS: Nói vậy đúng không em, anh chưa coi kỹ đó =))

đúng rồi đó, nó sẽ bị trùng, vậy là mình tốn gấp đôi bộ nhớ, đãng suy nghĩ cách tối ưu nó, loại bỏ các trường hợp trùng, tính dùng thread luôn, chia luồng chạy, rồi cộng lại

[11520126]

Leader có người hâm mộ kìa.

Mình chỉ hỏi vài thắc mắc ngoài lề nên ko tiện post lên đây thôi bạn.
P/s: mấy bạn vui lòng ghi rõ Vũ Hoàng ra nhé, ở đây 2 Hoàng lận =.=`!

[11520118]

{gioi han inp <32767 va ket qua <30 so hang}
const fi = 'bai3.inp';
fo = 'bai3.out';
max= maxint;

var
f: text;
so: array[1..max] of boolean;
stack: array[1..maxint] of longint;
kq: array[1..max,1..50] of longint;
x,t,tmin,skq: longint;

procedure nhap;
begin
assign(f,fi);
reset(f);
readln(f,x);
close(f);
end;

procedure khoitaoso;
var
i,j: longint;
check: boolean;
begin
so[1]:=false;
for i:=2 to x do so[i]:=false;
for i:=2 to x do
begin
check:=true;
for j:=2 to round(sqrt(i)) do if i mod j =0 then begin check:=false; break; end;
if check then so[i]:=true;
end;
tmin:=maxlongint;
t:=0;
for i:=1 to 50 do stack[i]:=0;
for i:=1 to x do
for j:=1 to 50 do kq[i,j]:=0;
t:=1;
end;

procedure luu;
var
i,j: integer;
begin
i:=1;
repeat
if stack[i]=0 then exit;
kq[skq,i]:=stack[i];
inc(i);
until false;
end;

procedure xuly(y,v: longint);
var
i: longint;
begin
if y=1 then exit;
stack[v]:=y;
if t>tmin then exit;
if (so[y]=false) and (t=tmin) then exit;
if (so[y]) and (t<tmin) and (t>1) then
begin
tmin:=t;
skq:=1;
luu;
exit;
end else
if (so[y]) and (t=tmin) then
begin
inc(skq);
luu;
exit;
end;
for i:=y downto 1 do
begin
if (so[i]) and (i<>x) then
begin
if y-i <= y div 2 then
begin
y:=y-i;
stack[v]:=i;
inc(t);
xuly(y,t);
dec(t);
y:=y+i;
end;
end;
end;
end;

procedure xuat;
var
i,j: longint;
begin
assign(f,fo);
rewrite(f);
writeln(f,skq);
for i:=1 to skq do
begin
for j:=1 to tmin do
begin
write(f,kq[i,j]);
if j<tmin then write(f,'+');
end;
writeln(f);
end;
close(f);
end;

begin
nhap;
khoitaoso;
xuly(x,1);
xuat;
end.


mình mạo muội post code bài 3 lên thử, các pro góp ý cho mình với :d mình chỉ biết pascal nên đây là bản 2.2.0.

đề nghị mọi người post code vào trang này cho nó dễ nhìn support tất cả các ngôn ngữ http://paste.ubuntu.com/

[11520118]

Bạn Hoàng làm ko gọi là sai! Vấn đề ở đây là giải thuật làm! Mình đag băn khoăn, ko biết khi làm bài ta nên làm theo kiểu chaỵ for xét thử 2 phần tử, r 3 phần tử thôi hay làm tổng quát hết là đúng. Bạn có đag theo dõi mấy bài viết trên ko vậy?? Mà hình như bạn cũg ko hiểu bạn Hoàng đag làm theo cách gì thì phải???

Chả theo cách gì cả, xem wiki nghĩ sao code vậy

[11520673]

Chả theo cách gì cả, xem wiki nghĩ sao code vậy

thì cách trên wiki là chỉ xét truong hợp tìm số có 2 phần tử or 3 phần tử thôi đó

[11520118]

P/S tìm được một bài hay, mọi người suy nghĩ luôn nhá
Hãy dùng ngôn ngữ lập trình (gì cũng được) để tính toán và xuất ra các cặp số n và k thỏa mãn:
1 + 2 + … + n = n + 1 + n + 2 + … + n + k

Input : Không có.
Output : Standard Output.
Output Format : In trên nhiều dòng, mỗi dòng là một cặp số n, k cách nhau bằng một hoặc nhiều khoảng trắng.

[11520126]

Chả theo cách gì cả, xem wiki nghĩ sao code vậy

Ờ, tuy wiki noi điều đó chưa được CM nhưng cũng chả ai nói điều đó là sai cả, mình cứ áp dụng tạm để giải quyết bài này thôi, hiện tại thì ko ai dám nói sai cả.
Còn ý của bạn Tú là ko biết nên làm tổng quát hay làm theo cái giả thuyết này thôi chứ gì ! Theo mình thì tùy mỗi người thôi, làm theo giả thuyết thì mình có lợi trong 1 bài toán, sau này ko áp dụng được giải thuật đó làm gì cả, nếu làm theo cách tổng quát thì có thể có lợi cho việc lập trình về sau. Mình cũng đã thử làm theo cách tổng quát rồi nhưng vẫn ko ra, time thì có hạn nên phải làm theo giả thuyết này như "phương án cuối cùng" vậy, sau này rãnh sẽ nghiên cứu giải thuật tổng quát sau.
Tóm lại bài làm nào mà đúng hết đáp số mẫu của người chấm thì bài đó là đúng, ko cần biết thuật toán ntn cả, quan trọng là mình có học được thêm exp nào từ bài toán đó ko thôi