Thảo luận thuật toán tối ưu cho bài toán Ramanujan và Euler

#1

Bài toán Ramanujan :
Xác minh tuyên bố này bằng cách viết một chương trình Ramanujan.cpp lấy đối số là một số nguyên n và in tất cả các số nguyên nhỏ hơn hoặc bằng n có thể được biểu diễn như là tổng lập phương theo 2 cách khác nhau.
Hint: tìm các số nguyên dương khác biệt a, b, c, và d sao cho a ^ 3 + b ^ 3 = c ^ 3 + d ^ 3. Sử dụng bốn vòng for lồng nhau.
Ví dụ, với n = 10000, ta có:
1729 = 1^3 + 12^3 = 9^3 + 10^3
4104 = 2^3 + 16^3 = 9^3 + 15^3
Suy ra, output: 1729 4104

Bài toán Euler :
Chứng minh phỏng đoán đó sai bằng cách tìm các số nguyên dương a, b, c, d và e sao cho:
a^5+b^5+c^5+d^5=e^5
Viết chương trình nhận vào từ bàn phím tham số NN và tìm kiếm vét cạn tất cả các lời giải với aa, bb, cc, dd và ee nhỏ hơn hoặc bằng NN. In các lời giải ra màn hình.

Cả 2 bài toán này mình dùng vòng lặp for chạy hết từ 1 đến n cho hết tất cả các số rồi tiến hành so sánh.
kết quả dễ đoán là chạy vào web bài tập thì gặp lỗi time limited .

Có bác nào từng làm bài này chưa, thuật toán tối ưu là gì nhỉ?

#2

Ý tưởng là a^3 < n -> a <= pow(n, 1/3)
chọn b khi đã chọn a thì b <= pow(n- a^3, 1/3)

a từ 1 -> pow(n, 1/3), lặp tiếp b từ 1-> pow(n- a^3, 1/3),
c từ 1-> pow(n, 1/3), d từ 1-> pow(n- c^3, 1/3).

Còn bạn lặp 4 vòng for O(n^4) mà n=10000 thì timeout là đúng rồi

#3

Chọn a, b, c tính d. O(n). 4 vòng lặp là dở.

2 Likes
#4 
#include <stdio.h>
#include <math.h>

int isRamanujan(int n)
{   
    
	int a,b,c,d,boolean,k;
	boolean=1;
	k=pow(n, 1/3);
	
    for (a=1;a<=k;a++)
    {
        k= pow((n-a*a*a), 1/3);
		for (b=1;b<=k;b++)
        {
        	k= pow((n-a*a*a-b*b*b), 1/3);
            for (c=1;c<=k;c++)
            {
            	k= pow((n-a*a*a-b*b*b-c*c*c), 1/3);
                for (d=1;d<=k;d++)
                {
                    if (((a*a*a+b*b*b)==(c*c*c+d*d*d)) && n==(a*a*a+b*b*b) && a!=b && b!=c && c!=d && b!=d && a!=d && a!=c) boolean=0;
                    
                }
            }
        }
    }
    
    return boolean;
    
}

int main()
{
    int n,i;
    scanf("%d", &n);
    
    for (i=1;i<=n;i++)
    {
        if (isRamanujan(i)==0) printf("%d ",i);
    }
    
    return 0;
    
}

sao giờ mình sửa theo bác mà không in ra gì :(.
cái trước của mình có in ra chỉ là hơi lâu thôi.

#5

1 chia 3 bằng 0 mà bạn :smiley:

#6

hjxx thế phải làm sao để căn bậc 3 hả bác ?

#7

Dùng tìm kiếm nhị phân thì có thể tìm căn bậc r của n:

def introot(n,r=2):
    lo,hi=0,n
    while lo!=hi-1:
        mid=(lo+hi)//2
        m=pow(mid,r)
        if m==n: return mid
        if m<n: lo=mid
        else: hi=mid
    return lo
1 Like
#8

câu 1 cho n tối đa là bao nhiêu, 10^5, 10^6 hay 10^9…

#9

O(n) mà sợ gì :slight_smile: 10^11 trở đi mới phê.

1 Like
#10

n < 10000 nghĩa là phải chạy x từ 1 tới 10000, chả lẽ mỗi lần xác định x có phải là số Ramanujan chỉ mất O(1) tức thì? Phải duyệt a từ 1 tới x1/3 như vậy tối thiểu cũng phải ~ O(n4/3) chứ?

#11

pow này là tượng trưng thôi.

Duyệt trên a, b, c suy ra d. O(n).

#12

10000 bác ơi :(…

#13

http://oeis.org/A001235

10000 thì copy mấy số trong list này rồi xuất những số < n thôi :smiling_imp:

1 Like
#14

vậy là 3 vòng lặp for lồng nhau à, chắc cách này hợp lý hơn

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?