حدس گلد باخ(سواله!)

  • شروع کننده موضوع شروع کننده موضوع monajem
  • تاریخ شروع تاریخ شروع
وضعیت
موضوع بسته شده است.
monajem

monajem

کاربر فوق‌حرفه‌ای
ارسال‌ها
933
امتیاز
0
نام مرکز سمپاد
علامه حلی اراک
شهر
اراک
مدال المپیاد
کامپیوتر-طلا
دانشگاه
صنعتی شریف
رشته دانشگاه
نرم افزار
بدون استفاده از آرایه،برنامه ای بنویسید که یک عدد بگیرد و 3 عدد اول که مجموعشان برابر آن عدد میشود چاپ کند.
 
پاسخ : حدس گلد باخ(سواله!)

بابا من بیشتر ازین حرفا ازتون انتظار داشتم!
 
پاسخ : حدس گلد باخ(سواله!)

به نقل از منجم! :
بدون استفاده از آرایه،برنامه ای بنویسید که یک عدد بگیرد و 3 عدد اول که مجموعشان برابر آن عدد میشود چاپ کند.
کلیک کنید تا باز شود...
الان دیدم! این سه تا عدد میتونن تکراری باشن دیگه؟ اگه نه گمونم صورت مساله اشکال داره! مثلا ۱۱ چی میشه؟
 
پاسخ : حدس گلد باخ(سواله!)

7+2+2
میتونن
 
پاسخ : حدس گلد باخ(سواله!)

بازگشتی هم گمونم بشه نوشت ...

کد: 
#include <stdio.h>

int prime(int n)
{
        int c;
        if (n < 2)
                return 0;
        for (c = 2; c < n; c++)
                if ((n % c) == 0)
                        return 0;
        return 1;
}

int maxprime(int max)
{
        int i, out;
        for(i = 2; i <= max; i++)
                if( prime( i ) )
                        out = i;
        return out;
}

int main()
{
        int t = 3, a, p;
        printf("Your number: ");
        scanf("%d", &a);
        if(a<6)
        {
                printf("Your number cannot be less than 6!\n");
                return 1;
        }
        printf("\n%d = ", a);
        while(t != 0)
        {
                t--;
                p = maxprime(a - 2 * t);
                printf("%d", p);
                if(t != 0)
                        printf(" + ");
                a = a - p;
        }
        printf("\n");
        return 0;
}

میاد بزرگ ترین عدد اول قبل از عدد ورودی ما (اسمش رو میزاریم a) رو حساب میکنه (اسمش رو میزاریم p)، حالا تلاش میکنه که ۲ تا عدد اول پیدا کنه که مجموعش بشه اون p-a ... البته الان که بهش فکر میکنم میبینم غلطه!
 
پاسخ : حدس گلد باخ(سواله!)

نه، ببخشید ... برای عدد های بزرگ سوتی میده!
الان درستش میکنم ...

گمون نکنم جواب من اشکال داشته باشه، ولی برای ۱۰۰۰۰ اشکال داره ...
۱۰۰۰۰ رو نمیتونه با ۳ تا عدد بنویسه برنامه ی من ... ولی با ۴ تا میشه ...

خب کمک کنید debug کنم دیگه! ایده ی دیگه ی به ذهنتون میرسه؟
 
پاسخ : حدس گلد باخ(سواله!)

دیگه درست شد ... فقط کد شدیدن خرکی هست!
کد: 
#include <stdio.h>

int p1, p2, p3, s1 = 0, s2 = 0, s3 = 0;
int prime(int n)
{
        int c;
        if (n < 2)
                return 0;
        for (c = 2; c < n; c++)
                if ((n % c) == 0)
                        return 0;
        return 1;
}

int maxprime(int input, int n)
{
        int i, t, s;
        if(n==1)
                s=s3;
        else if(n==2)
                s=s2;
        else if(n==3)
                s=s1;

        for(i = input - 2 * n + 2; i >= 2; i--)
                if( prime( i ) )
                {
                        t = i;
                        if(s==0)
                                break;
                        else if(n==1)
                                s--;
                        else if(n==2)
                                s--;
                        else if(n==3)
                                s--;
                }
        if(n == 3)
                p1 = t;
        else if(n == 2)
                p2 = t;
        else if(n == 1)
                p3 = t;
        if(n != 1)
                maxprime(input-t, n-1);
        else if(n == 1 && t != input)
        {
                if(p1 == 2)
                {
                        if(p2 == 2)
                        {
                                if(p3 == 2)
                                        return 1;
                                else
                                        s3++;
                        }
                        else
                                s2++;
                }
                else
                        s1++;
                maxprime(input+p1+p2, 3);
        }
        return 0;
}

int main()
{
        int input;
        printf("Your number: ");
        scanf("%d", &input);
        if(input<6)
        {
                printf("Your number cannot be less than 6!\n");
                return 1;
        }
        maxprime(input, 3);
        printf("%d = %d + %d + %d\n", input, p1, p2, p3);
        return 0;
}
 
پاسخ : حدس گلد باخ(سواله!)

باز هم سریعتر از کد قبلی: (اصلاح شد)
کد: 
#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;

const int MAXN = 10*1000*1000 + 10;

int n;
bool isc[MAXN]; //isc[i] = Is i a composite number?
vector<int> prm;

void sieve()
{
	isc[1] = true;
	for(int i=2; i<=n; i++)
		if(!isc[i])
		{
			prm.push_back(i);
			for(int j=i; j<=n/i; j++)
				isc[j*i] = true;
		}
}

int main()
{
	scanf("%d", &n);
	sieve();
	for(int i=0; i<(n % 2 ? prm.size() : 1); i++)
		for(int j=i; j<prm.size(); j++)
		{
			int d = prm[i] + prm[j];
			if(d <= n && n-d >= prm[j] && !isc[n-d])
					printf("%d = %d + %d + %d\n", n, prm[i], prm[j], n - d);
		}
	return 0;
}
 
پاسخ : حدس گلد باخ(سواله!)

به هر حال آفرین
ولی من با این زبون! آشنایی ندارم میشه یه خورده از الگوریتمو بگی؟(میخوای تو بیسیک بنویس)
 
پاسخ : حدس گلد باخ(سواله!)

توضیح: اول با الگوریتم غربال اراتستن می‌بینیم که کدوم اعداد بین ۱ تا n اول هستن. (تابع sieve)
بعدش میایم دو تا عدد دلخواه از بین اعداد اول پیدا شده (مثل a و b) رو انتخاب می‌کنیم.
حالا می‌بینیم که n - a - b اول هست یا نه.
(البته برای nهای زوج، چون مطمئنیم که یکی از اعدادمون ۲ هست، کافیه بگیم a=2)

تحلیل‌زمانی: غربال اراتستن [tex]O(n lg{lg{n}})[/tex] هستش.
با توجه به اینکه تعداد اعداد اول بین ۱ تا n، از [tex]O(n/lg{n})[/tex] هست، برای تعیین a و b [tex]O((n/lg{n})^2)[/tex] خرج می‌کنیم. (در حالت n زوج، [tex]O(n/lg{n})[/tex])
برای اینکه ببینیم n - a - b اول هست یا نه، [tex]O(1)[/tex] خرج می‌شه.
پس در کل، برای nهای فرد، الگوریتم [tex]O((n/lg{n})^2)[/tex]برای nهای زوج، از [tex]O(n lg{lg{n}})[/tex] هستش.
 
پاسخ : حدس گلد باخ(سواله!)

غربال از آرایه استفاده می کنه و تو صورت سوال گفته استفاده نکنید! پس احتمالا نیتش این بوده که عدد کوچک بده..
فقط اینکه حالا اگه فرض کنیم عددمون 1 یا 2 یا 3 یا 4 بود..اینا که اصلا نمیشن. خب برای عددهای بزرگتر می تونیم بیایم 3 تا از عدد های فرد کم کنیم بعد حاصلش زوج می شه و طبق گلدباخ اون 2 تای دیگه هم پیدا می شن. اگر هم زوج بود که 2 رو بر می داریم و هر چی موند رو با گلدباخ براش دو تا عدد پیدا می کنیم.
گلدباخ معمولیم که همه بلدن.. (البته با غربال و آرایه!) اگر بخوایم بدون آرایه حل کنیم باید هر بار اول بودن عدد رو چک کنیم.. ( خسته می شیم )
 
وضعیت
موضوع بسته شده است.
Back
بالا