Từ 1 số p phân tích ra tổng rồi tìm tích lớn nhất

[AlexF]

anh em trong diễn đàn có thể gợi ý cho mình thuật toán làm bài này được không

cho 1 số nguyên dương p
phân tích p ra thành tổng các số nguyên dương
in ra màn hình cặp gồm nhiều số có tổng là P và có tích lớn nhất

[Berberin]

Tớ mới chỉ tìm được 1 cận dưới khá tốt, đánh giá dựa trên BĐT Cauchy, chưa khẳng định đc đây có phải là kết quả ko. Mọi người cho ý kiến nhá.

/*http://forums.congdongcviet.com/showthread.php?t=9055(c) Berberin*/  #include <iostream>#include <cstdlib>#include <cmath> using namespace std;//////////////////////////////////////////////////////////////////////////////////////int main(){     unsigned S = 10;            /*Cauchy    for (unsigned n = 1; n<=S; n++)        cout <<n <<'\t' <<float(S)/n <<'\t' <<powf(float(S)/n, n) <<endl;       cout <<endl;    */       unsigned P = S, N = 1;      for (unsigned n = 2; n<S; n++){        unsigned x = S/n;        unsigned p = powf(x, n-S%n)*powf(x+1, S%n);             if (p > P){            P = p;            N = n;        }    }        cout <<"Result: " <<endl;    cout <<S <<"--> (" <<S/N <<"^" <<N-S%N <<')';    if (S%N > 0)        cout <<"x(" <<S/N+1 <<"^" <<S%N <<")";    cout <<" = " <<P <<endl;     system("pause");    return EXIT_SUCCESS;}//////////////////////////////////////////////////////////////////////////////////////

[SmallInt]

cho 1 số nguyên dương p
phân tích p ra thành tổng các số nguyên dương
in ra màn hình cặp gồm nhiều số có tổng là P và có tích lớn nhất

Tức là phân tích p ra thành tổng nhiều số ah`,hay chỉ là 2 số thôi rồi tìm xem cặp nào có tích lơn nhất..Bạn thử ví dụ được không?

[AlexF]

thich ra bao nhieu so chang duoc,quan trọng là không lẫn số âm là được

to Berberin

mình nghĩ bài của cậu co van de,cậu thử với số 100 nha,đáp số của cậu nhỏ hơn đáp số của mình rất nhiều mình cũng mới chứng minh bằng toán học được rằng để tích lớn nhất thì bắt buộc phải phân tích ra n lần số 3 và k lần số 2 trong đó 3 được ưu tiên trước và 2 được dùng để lấp chỗ trống của 3 ( k chỉ có thể =0 hoặc 1 hoặc 2 )
x= 3*m +2*k ( với k chỉ có thể =0 hoặc 1 hoặc 2 )
day la code cua minh

#include<iostream>#include<stdlib.h>#include<math.h>#include <iomanip.h>int main(){    int a,solan3;    float solan2;    std::cout<<"NHAP SO CAN PHAN TICH A: ";    std::cin>>a;    solan3=a/3;    solan2= float( a - solan3 * 3 ) / 2;    if( a - solan3 * 3 <2&&a-solan3 *3 !=0)    {        solan3=a/3-1;        solan2= ( a - solan3 * 3 ) / 2;    }    if(solan2!=0){    std::cout<<"so da cho A = "<<a<<" duoc phan tich : 3 x "<<solan3<<"+ 2 x "<<solan2<<" = "<<3*solan3 +2*solan2;    std::cout<<"\n TICH MAX LA: 3^"<<solan3<<" x 2^"<<solan2<<" = "<<setiosflags(ios::showpoint) << setprecision(100) <<pow(3,solan3)*pow(2,solan2);    }    else    {        std::cout<<"so da cho A = "<<a<<" duoc phan tich : 3 x "<<solan3<<"+ 2 x "<<solan2<<" = "<<3*solan3 +2*solan2;        std::cout<<"\n TICH MAX LA: 3^ "<<solan3<<" = "<<setiosflags(ios::showpoint) << setprecision(100) <<pow(3,solan3)*pow(2,solan2);    }    system("pause");    return 0;}

đây là bài của cậu với số 100

#include <iostream>#include <cstdlib>#include <cmath> using namespace std;//////////////////////////////////////////////////////////////////////////////////////int main(){    unsigned S = 100;           /*Cauchy    for (unsigned n = 1; n<=S; n++)        cout <<n <<'\t' <<float(S)/n <<'\t' <<powf(float(S)/n, n) <<endl;       cout <<endl;    */      unsigned P = S, N = 1;     for (unsigned n = 2; n<S; n++){        unsigned x = S/n;        unsigned p = powf(x, n-S%n)*powf(x+1, S%n);            if (p > P){            P = p;            N = n;        }    }       cout <<"Result: " <<endl;    cout <<S <<"--> (" <<S/N <<"^" <<N-S%N <<')';    if (S%N > 0)        cout <<"x(" <<S/N+1 <<"^" <<S%N <<")";    cout <<" = " <<P <<endl;     system("pause");    return EXIT_SUCCESS;}

[Berberin]

thich ra bao nhieu so chang duoc,quan trọng là không lẫn số âm là được

mình nghĩ bài của cậu co van de,cậu thử với số 100 nha,đáp số của cậu nhỏ hơn đáp số của mình rất nhiều

Do tớ dùng kiểu unsigned nên bị tràn, thay kiểu của 2 biến p và P là ok. Chẳng hạn với unsigned long long p, P

Result:
100--> (3^32)x(4^1) = 7412080613261312

mình cũng mới chứng minh bằng toán học được rằng để tích lớn nhất thì bắt buộc phải phân tích ra n lần số 3 và k lần số 2 trong đó 3 được ưu tiên trước và 2 được dùng để lấp chỗ trống của 3 ( k chỉ có thể =0 hoặc 1 hoặc 2 )
x= 3*m +2*k ( với k chỉ có thể =0 hoặc 1 hoặc 2 )

Thế hả, kq đẹp nhỉ, xin chúc mừng . Cách của tớ ko đẹp nhưng cũng cm xong rồi, nếu xét thêm tí nữa chắc cũng thu đc kq của cậu nhưng tớ lười nên xài vòng for .

[blackpawn]

Bài này bản chất là một bài toán mà ^^. Kết quả của bạn coder gate đúng rồi . Nếu mình nhớ không nhầm, hình như đây là một bài thi trong series của Topcoder, đã từng được anh rox_rook giới thiệu trên forum mình một lần.
Chúc mừng bạn coder_gate nghen!

[AlexF]

/*http://forums.congdongcviet.com/showthread.php?t=9055(c) Berberin*/  #include <iostream>#include <cstdlib>#include <cmath> using namespace std;//////////////////////////////////////////////////////////////////////////////////////int main(){     unsigned long S = 100;           /*Cauchy    for (unsigned n = 1; n<=S; n++)        cout <<n <<'\t' <<float(S)/n <<'\t' <<powf(float(S)/n, n) <<endl;       cout <<endl;    */      unsigned long  P = S, N = 1;     for (long n = 2; n<S; n++){        long x = S/n;        unsigned long p = powf(x, n-S%n)*powf(x+1, S%n);            if (p > P){            P = p;            N = n;        }    }       cout <<"Result: " <<endl;    cout <<S <<"--> (" <<S/N <<"^" <<N-S%N <<')';    if (S%N > 0)        cout <<"x(" <<S/N+1 <<"^" <<S%N <<")";    cout <<" = " <<P <<endl;     system("pause");    return EXIT_SUCCESS;}

Do tớ dùng kiểu unsigned nên bị tràn, thay kiểu của 2 biến p và P là ok. Chẳng hạn với unsigned long long p, P


Result:
100--> (3^32)x(4^1) = 7412080613261312

híc,tràn số hay không thì tớ kô rõ nhưng mà dù có sửa bài cậu hay là để nguyên thì giá trị vẫn trả về là 2^17 * 3^22 mà,dù không thực hiện phép nhân mình cũng biết chắc chắn nó sẽ nhỏ hơn kết quả của mình
đã chứng minh roài ...

[Berberin]

Uhm, cậu có đọc code của tớ không vậy? Hay chỉ F5? Trong vòng for đó chứa cách làm của cậu đấy, vậy nó sai thế nào được?

Do tớ dùng kiểu unsigned nên bị tràn, thay kiểu của 2 biến p và P là ok. Chẳng hạn với unsigned long long p, P

Đề nghị thêm 1 chữ long nữa đi, 1 long hơi ngắn.

Đây là kq của bài của cậu với số cần phân tích = 100

NHAP SO CAN PHAN TICH A: 100
so da cho A = 100 duoc phan tich : 3 x 32+ 2 x 2 = 100
 TICH MAX LA: 3^32 x 2^2 = 7412080613261312.000000000000000000000000000000000000000000000000000000000000000000000000000000000000

[AlexF]

Chẳng hạn với unsigned long long p, P

mình chưa từng biết đến kiểu này,mà có thử cũng báo lỗi....có gì xin bạn chỉ giáo

[thành viên mới]

Post bài chứng minh nên đi xem nào sao cứ nói xuông vậy