[isteam test 2011] k4,5,6

[07520004]

27tr @@! Bài của mình chỉ xuất ra các đáp án có số phần tử ít nhất thôi, chứ xuất hết thì pó tay. Mai T post bài 3 của T lên xem thử ngheng.

uh để mai qua máy kia t post lên! Uh bài bạn chỉ tìm các tổ hợp có 2,3 phần tử nên chạy nhanh hơn cách t r!

Bài 3, xuất hết tất cả các cách phân tích n thành tổng những số hạng nguyên tố với số lượng số hạng ít nhất

Nằm trong khuôn khổ chiến dịch PR thô bạo cho mã nguồn mở nên code sẽ được viết bằng python, giải thuật thiết kế theo nguyên tắc tham lam nên chắc nó còn hơi ngu ngu nhưng mà kệ, viết giải trí mà, ai thấy chỗ sai chỉ ra giùm chứ đừng nói lời cay đắng.

Đã test với số n = 5 chục ngàn, chạy mất khoản 4MiB ram thời gian khoảng vài phút tính toán sau đó mất vài chục phút để xuất hết kết quả ra màn hình =))
Thuật toán có độ phức tạp có lẽ là nằm đâu đó giữa n^2 với n^3 (làm biếng tính quá) nên nếu 50.000 mà chạy vài phút thì nếu chờ vài tiếng có thể tăng nó lên 60 căn hai là 7 lần nữa, nhưng mà khuya rồi

Ai có thắc mắc về python xin mời ghé đại bản doanh box mã nguồn mở: http://forum.uit.edu.vn/forums/57-Lop-ma-nguon-mo
Hoặc ghé văn phòng tụ tập đập phá: http://forum.uit.edu.vn/threads/1931...a-se-thu-linux

import math

n = 46
print "Nhap n "
n = int(raw_input())

def prime_list(n):
	result = range(2,n)
	i = 0
	b = math.sqrt(n)
	while i < len(result) and result[i] < b :
#		print result[i]
		a = 2 * result[i] 
		j = i + 1
		while j < len(result):
#			print 'a = ' + str(a)
			if (result[j] == a):
#				print 'pop ' , result[j]
				result.pop(j)
				a += result[i]
			elif (result[j] > a):
				a += result[i]
			j += 1

		i += 1
	return result
print prime_list(n)


pl = prime_list(n)
min_number = len(pl)
cur_number = -1



a = 0
while (len(pl) > 0 and (cur_number == -1 or cur_number <= min_number)):

	#init value
	backup = pl[:] #clone array
	result = [] #define blank array
	while (a < n and len(backup) > 0):
		if (a + backup[-1] <= n):
			a += backup[-1]	
			result.append(backup[-1])
		else:
			backup.pop()
	cur_number = len(result)
	if (a == n and cur_number <= min_number):

		print "result: ", result
		min_number = min( cur_number, min_number)
	else:
		cur_number = 0		
		pass
	#reset value
	a = 0
	pl.pop() #decree the list after each result found, so that next result will be different

PS: Các bạn đọc code python thấy nó dễ hiểu không vậy? Chắc cảm giác giống nãy giờ anh đọc code pascal thôi =)). code dễ hiểu mà ha, ai thấy sai cứ chỉ, ai không hiểu cứ hỏi.

1st revision: Hàm tìm số nguyên tố sai. Đã update

[11520126]

PS: Các bạn đọc code python thấy nó dễ hiểu không vậy? Chắc cảm giác giống nãy giờ anh đọc code pascal thôi =)). code dễ hiểu mà ha, ai thấy sai cứ chỉ, ai không hiểu cứ hỏi.

Đúng là em chả hiểu gì cả, hjx! Code này cho chạy trên CodeBlock lun hả anh An??? Anh chỉ em cách tạo project lun cái, hình như chọn win32Gui hả ? Em thì ngoài Pascal ra, còn lại mù tịt.
Ủa mà này giờ anh thức viết code bài này đấy à @@!

[10520101]

Câu 3 của mình

#include "stdafx.h"
#include "conio.h"
#include "iostream"
using namespace std;
int a[1000],d=0;
int nguyento(int a)
{
    int kq=1,i;
    if(a<2)return 0;
	else	
		if(a==2||a==3) return 1;
		else
		for(i=2;i<a;i++)
		{
			if (a%i==0)
				return 0;
        
		}
		return kq;
}/*=======================================*/
void khoitaonguyento(int n)
{
	
	for(int i=n-1;i>1;i--)
		if(nguyento(i) )
			{
				a[d]=i;
				d++;
			}
		
}
/*========================================*/
void ngtosochan(int n)
{
		int i;
		for(i=n/2;i<n;i++)
		{
			if(nguyento(i)&&nguyento(n-i) ) 
			{
				/*a=i;
				b=n-i;*/
				cout<<endl;
				cout<<n<<"="<<i<<"+"<<n-i;
			}	
		}
}
/*=======================================*/
void ngtosole(int n)
{
	int i,j,k,h=0;
	if(nguyento(n-2)) cout<<n<<"="<<n-2<<"+"<<2;
	else
	{
		for(i=0;i<d;i++)
			for(j=i;j<d;j++)
				for(k=j;k<d;k++)
					if((a[i]+a[j]+a[k])==n) {h++; cout<<n<<"="<<a[i]<<"+"<<a[j]<<"+"<<a[k]<<endl;}
	}

}
void main()
{
	int n;
	cout<<"\n Nhap so n:=";
	cin>>n;
	/* 
	-Neu n chan: n co the phan tich thanh toi thieu 2 so nguyen to
	-Neu n le: n co the phan tich thanh toi thieu
		+2 so
		+3 so
		*/
	if(n%2==0) ngtosochan(n);
	else 
		{
			khoitaonguyento(n);
			ngtosole(n);
	}
	getch();
}

[07520004]

Đúng là em chả hiểu gì cả, hjx! Code này cho chạy trên CodeBlock lun hả anh An??? Anh chỉ em cách tạo project lun cái, hình như chọn win32Gui hả ? Em thì ngoài Pascal ra, còn lại mù tịt.
Ủa mà này giờ anh thức viết code bài này đấy à @@!

Python chạy bằng python. Qua box mã nguồn mở tạo topic đi em, cái này tối quỡn quỡn dợt tay nghề ấy mà

[10520101]

Test với số 46 luôn, thiếu rất nhiều trường hợp:

python sum_of_prime.py 
Nhap n 
46
[2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45]
result:  [43, 3]
result:  [41, 5]
[COLOR="#FF0000"]result:  [39, 7][/COLOR]
[COLOR="#FF0000"]result:  [37, 9][/COLOR]
[COLOR="#FF0000"]result:  [35, 11][/COLOR]
[COLOR="#FF0000"]result:  [33, 13][/COLOR]
[COLOR="#FF0000"]result:  [31, 15][/COLOR]
result:  [29, 17]
[COLOR="#FF0000"]result:  [27, 19][/COLOR]
[COLOR="#FF0000"]result:  [25, 21][/COLOR]
result:  [23, 23]

versus:

~/test $ ./a.out 

 Nhap so n:=46

46=23+23
46=29+17
46=41+5
46=43+3

Các cặp số màu đỏ đâu phải là các cặp số nguyên tố đâu anh?

[07520004]

Câu 3 của mình

#include "stdafx.h"
#include "conio.h"
#include "iostream"
using namespace std;
int a[1000],d=0;
int nguyento(int a)
{
    int kq=1,i;
    if(a<2)return 0;
	else	
		if(a==2||a==3) return 1;
		else
		for(i=2;i<a;i++)
		{
			if (a%i==0)
				return 0;
        
		}
		return kq;
}/*=======================================*/
void khoitaonguyento(int n)
{
	
	for(int i=n-1;i>1;i--)
		if(nguyento(i) )
			{
				a[d]=i;
				d++;
			}
		
}
/*========================================*/
void ngtosochan(int n)
{
		int i;
		for(i=n/2;i<n;i++)
		{
			if(nguyento(i)&&nguyento(n-i) ) 
			{
				/*a=i;
				b=n-i;*/
				cout<<endl;
				cout<<n<<"="<<i<<"+"<<n-i;
			}	
		}
}
/*=======================================*/
void ngtosole(int n)
{
	int i,j,k,h=0;
	if(nguyento(n-2)) cout<<n<<"="<<n-2<<"+"<<2;
	else
	{
		for(i=0;i<d;i++)
			for(j=i;j<d;j++)
				for(k=j;k<d;k++)
					if((a[i]+a[j]+a[k])==n) {h++; cout<<n<<"="<<a[i]<<"+"<<a[j]<<"+"<<a[k]<<endl;}
	}

}
void main()
{
	int n;
	cout<<"\n Nhap so n:=";
	cin>>n;
	/* 
	-Neu n chan: n co the phan tich thanh toi thieu 2 so nguyen to
	-Neu n le: n co the phan tich thanh toi thieu
		+2 so
		+3 so
		*/
	if(n%2==0) ngtosochan(n);
	else 
		{
			khoitaonguyento(n);
			ngtosole(n);
	}
	getch();
}

Chạy tốt với số chẵn. Qua tới số lẻ thì segfault:

$ ./a.out 

 Nhap so n:=49993
Segmentation fault

[07520004]

Các cặp số màu đỏ đâu phải là các cặp số nguyên tố đâu anh?

Ừ, code ban đầu của anh sai, đã update

[10520101]

Chạy tốt với số chẵn. Qua tới số lẻ thì segfault:

$ ./a.out 

 Nhap so n:=49993
Segmentation fault

Tại vì số lẽ có đến 3 cách phân tích mà chưa biết cách làm sao cho tối ưu

[07520004]

Tại vì số lẽ có đến 3 cách phân tích mà chưa biết cách làm sao cho tối ưu

Áp dụng lý thuyết toán vào là tối ưu nhất rồi.

/*
-Neu n chan: n co the phan tich thanh toi thieu 2 so nguyen to
-Neu n le: n co the phan tich thanh toi thieu
+2 so
+3 so
*/

Cái này là lấy trong sách ra hả, anh chả nhớ gì hết. Greedy mà tán =))

[11520126]

Cái này là lấy trong sách ra hả, anh chả nhớ gì hết. Greedy mà tán =))

Lấy ở đây nè anh: Lời giải cho Giả Thuyết Goldbach - Euler và 2 Định lý mới về số nguyên tố

[07520004]

Tại vì số lẽ có đến 3 cách phân tích mà chưa biết cách làm sao cho tối ưu

Sửa giùm em nè

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
int* a, d;
int nguyento(int a)
{
    int kq=1,i;
    if(a<2)return 0;
	else	
		if(a==2||a==3) return 1;
		else
		for(i=2;i<a;i++)
		{
			if (a%i==0)
				return 0;
        
		}
		return kq;
}/*=======================================*/
void runEratosthenesSieve(int upperBound) {

      int upperBoundSquareRoot = (int)sqrt((double)upperBound);

      bool *isComposite = new bool[upperBound + 1];
	a = new int [upperBound+1];
      memset(isComposite, 0, sizeof(bool) * (upperBound + 1));

      for (int m = 2; m <= upperBoundSquareRoot; m++) {

            if (!isComposite[m]) {

                  for (int k = m * m; k <= upperBound; k += m)

                        isComposite[k] = true;

            }

      }

	d = 0;
      for (int m = upperBoundSquareRoot; m <= upperBound; m++)

            if (!isComposite[m]){

			a[d++] = m;

		}

      delete [] isComposite; 

}
/*========================================*/
void ngtosochan(int n)
{
		int i,j;

		for(i=0;i<d;i++)
			for(j=i;j<d;j++)
				if((a[i]+a[j])==n) { 			cout<<n<<"="<<a[i]<<"+"<<a[j]<<endl;}
}
		

/*=======================================*/
void ngtosole(int n)
{
	int i,j,k,h=0;
	if(nguyento(n-2)) cout<<n<<"="<<n-2<<"+"<<2;
	else
	{
		for(i=0;i<d;i++)
			for(j=i;j<d;j++)
				for(k=j;k<d;k++)
					if((a[i]+a[j]+a[k])==n) {h++; cout<<n<<"="<<a[i]<<"+"<<a[j]<<"+"<<a[k]<<endl;}
	}

}

int main()
{
	int n;
	cout<<"\n Nhap so n:=";
	cin>>n;
	/* 
	-Neu n chan: n co the phan tich thanh toi thieu 2 so nguyen to
	-Neu n le: n co the phan tich thanh toi thieu
		+2 so
		+3 so
		*/
	if(n%2==0) ngtosochan(n);
	else 
		{
			runEratosthenesSieve(n);
			ngtosole(n);
	}
	
	return 0;

}

Lấy ở đây nè anh: Lời giải cho Giả Thuyết Goldbach - Euler và 2 Định lý mới về số nguyên tố

Cái này hình như không nằm trong chương trình học thì phải, may quá đỡ nhục =))

[11520126]

Hjx, mù mấy cái này quá, ko có bình luận gì thêm.
Giờ h post nốt code bài 1, chắc là ổn:

program bai_1;
uses crt;
var  s,a,b,kq:string;
     c,i,n,x,y,z,g:integer;
begin
clrscr;
Write('Nhap chuoi 1:'); readln(a);
Write('Nhap chuoi 2:'); readln(b);
writeln;

x:=length(a);
y:=length(b);
If x>y then
           begin
           z:=x-y;
           For i:=1 to z do
           b:='0'+b;
           end;
If y>x then
           begin
           z:=y-x;
           For i:=1 to z do
           a:='0'+a;
           end;


Writeln(a);
writeln('+');
Writeln(b);
n:=length(a);
z:=0;
For i:=n downto 2 do
 begin
 val(a[i],x,g);
 val(b[i],y,g);
 c:=x+y+z;
 If c>=10 then
            begin
            str(c,s);
            val(s[1],z,g);
            kq:=s[2]+kq;
            end
          else
            begin
            z:=0;
            str(c,s);
            kq:=s+kq;
            end;
end;

val(a[1],x,g);
val(b[1],y,g);
c:=x+y+z;
str(c,s);
kq:=s+kq;

for i:=1 to length(kq) do write('-');
Writeln;
Writeln(kq);
readln;
end.

[mikun93]

của bạn cũng bị ngay cái trc 1900 nhỉ?hix mà code tính năm đó mình đọc cũng ko hiểu! bạn tự nghĩ ra hả?

Toàn bộ thuật tính ngày là mình nghĩ đó bạn Tú ^^ sếp Hoàng nhaz, chơi e ghê wa >.<

[11520126]

Toàn bộ thuật tính ngày là mình nghĩ đó bạn Tú ^^ sếp Hoàng nhaz, chơi e ghê wa >.<

??!!! Tớ có làm gì cậu đâu.

[10520214]

Mình đưa thử bài mình các bạn xem thử luôn nha

#include "stdafx.h"
#include <iostream>
#include "conio.h"
#include "math.h"
using namespace std;

bool test(int n);
void result(int n);

bool test(int n)
{
if(n<2)return 0;
for(int i=2;i<=sqrt((double)n);++i)
if(n%i==0)return 0;
return 1;
}
void result(int n)
{
int count=0;int j=0;
tt: for(int i=2;i<=(n-j)/2;++i)
{
if(test(i)!=0 && test(n-j-i)!=0)
if(j) cout<<j<<"+"<<i<<"+"<<n-j-i<<endl;
else
{
cout<<i<<"+"<<n-i<<endl;
count++;
}
}
if(count==0) for(j=j+1;j<(n-j)/2;++j)
{if(test(j)) goto tt;}
}

int _tmain(int argc, _TCHAR* argv[])
{
int n;
c: do
{
cout<<"\n\nEnter n: ";cin>>n;
}while(n<=1);
if(n==2||n==3) cout<<"Can not be split into the sum of two primes\n";
else result(n);
cout<<"Do you want to continue and try to numberic other (Y/N)";
char c=getch();
if(c=='y'||c=='Y') goto c;
return 0;
}