Goldbach je muj nepritel prosim o pomoc – Pascal – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

Goldbach je muj nepritel prosim o pomoc – Pascal – Fórum – Programujte.comGoldbach je muj nepritel prosim o pomoc – Pascal – Fórum – Programujte.com

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
Pepca0
Duch
7. 11. 2007   #1
-
0
-

Mam takoveto zadaní
Slavná Goldbachova hypotéza říká, že každé sudé číslo větší než dva se dá zapsat jako součet dvou (ne nutně různých) prvočísel. Dokázat se nám ji asi nepodaří, ale pojďme si ji aspoň vyzkoušet pro malá čísla.

Na standardním vstupu jsou zadána přirozená čísla (každé na samostatném řádku, ukončena nulou). Vypište pro každé z nich buďto řádek X=A+B, kde X je zadané číslo, a A a B jsou prvočísla se součtem X, nebo, pokud rozklad neexistuje, řádek s textem "Ouch!". Můžete předpokládat, že čísla na vstupu nepřekročí 1000000.

Aby byl výstup vašeho programu jednoznačný, vypište rozklad, v němž je A≤B a A je nejmenší možné.

Poznámka: Jednička není prvočíslo :-)

Příklad: Pro vstup:
4
6
8
11

je správný výsledek:
4=2+2
6=3+3
8=3+5
Ouch!


Neni problem napsat na toto program ja mam problem s casovou slozitosti mohl by mi nekdo poradit jak to napsat co nejefektivnejsi (nejrychlejsi. Dekuji za pomoc

Nahlásit jako SPAM
IP: 85.70.1.–
Reklama
Reklama
spam je píča všichni jsou píča
~ Anonymní uživatel
1 příspěvek
10. 11. 2007   #2
-
0
-

spam je píča všichni jsou píča

Nahlásit jako SPAM
IP: 213.195.230.–
Michal
~ Anonymní uživatel
624 příspěvků
22. 11. 2007   #3
-
0
-

Ahoj, nejsi náhodou v prváku na matfyzu? Že by úloha z programování?:-)

Nahlásit jako SPAM
IP: 212.24.150.–
x.dee.x0
Duch
3. 12. 2008   #4
-
0
-

To Pepca :
Ahoj, náhodou, nevíš už, jak se to má napsat? Zkoušela jsem to, ale nedopadlo to zatím.
Přeju hodně úspěchů :o)

Nahlásit jako SPAM
IP: 213.226.245.–
KIIV+42
God of flame
3. 12. 2008   #5
-
0
-

no tak vygeneruj si nejdriv prvocisla do nejakyho limitu pomoci eratosthenova sita
a pak muzes uz kombinovat ... jen je otazkou zda to delat jako kazdy s kazdym z toho vysitovanyho souboru prvocisel nebo brat ty sudy cisla a zkouset je davat dohromady... hadam ale ze kombinovat ty prvocisla bude rychlejsi...
pak asi ideal bude mit jeste pole ... a budes si znacit cisla (na dane pozici v poli jako ze maji soucet...)

neco jako: (prodpoklada se ale ze uz tam budou jen prvocisla... tj index 1)

for i:=1 to 1000 do
for j:=1 to 1000 do begin
sude[ (prvocisla[i]+prvocisla[j]) div 2 ] = 1 ; (* nebudem zbytecne plytvat pameti... liche cisla netreba *)
end;

a nakonec jen projedes vse... jo pocitat s tim ze maximalni index pole bude vlastne posledni prvocislo ktery mas v poli prvocisla...

urcite to usetri hodne 1) nemusis testovat ktery cislo je prvocislo.. mas to rovnou vygenerovany
2) nemusis brat ty sudy cisla a hledat ktery dve prvocisla k nim pasujou...

nevyhoda bude pokud budes chtit treba do 100000000 tak uz to ukousne skoro pul giga ram :)

Nahlásit jako SPAM
IP: 80.250.27.–
Program vždy dělá to co naprogramujete, ne to co chcete...
o-lox0
Super člen
4. 12. 2008   #6
-
0
-

To KIIV :
já bych to -něco jako- vylepšil možná takhle abychom boostovali...
for i:=1 to 1000 do
for j:=1000 downto i do begin
suma:=prvocisla[i]+prvocisla[j];
for k:=1 to vstupu do If vstup[k]=suma then ... {mame i+j, citadlo++}
If citadlo=vstupu then konec {nebude ouch}
end;

a ta 1000 se da udelat plovouci podle numera na vstupu

Nahlásit jako SPAM
IP: 85.71.152.–
joe
~ Anonymní uživatel
62 příspěvků
4. 12. 2008   #7
-
0
-

Já při prvním spuštění vygeneruju prvočísla a uložím je do souboru, ze kterého je pak při každém dalším spuštění načítám (místo generování). Běhá to bleskově :smile1:

Nahlásit jako SPAM
IP: 213.211.51.–
KIIV+42
God of flame
4. 12. 2008   #8
-
0
-

To joe : jo to taky neni vubec blbej napad :D ... urcite me nekdy napad akorat sem se ubranil... :o) j/k

Nahlásit jako SPAM
IP: 80.188.94.–
Program vždy dělá to co naprogramujete, ne to co chcete...
x.dee.x0
Duch
6. 12. 2008   #9
-
0
-

Ahoj, nemáte někdo napsaný ten program komplet? Zkouším, zkouším,...,nefunguje :-(
Pomóc prosím

Nahlásit jako SPAM
IP: 213.226.245.–
KIIV+42
God of flame
6. 12. 2008   #10
-
0
-

zkousej po malejch castech...
nejdriv rozjet treba prvocisla... pak kombinace...

Nahlásit jako SPAM
IP: 77.237.136.–
Program vždy dělá to co naprogramujete, ne to co chcete...
o-lox0
Super člen
6. 12. 2008   #11
-
0
-

EDIT : to je zrada :-)

Srovnáme rychlosti už zhotovených ??
zvolil jsem si čísla do 1400000 - 10 náhodných hodnot
578 milisekund - mojí verzí :-)

Nahlásit jako SPAM
IP: 85.71.152.–
evandar0
Newbie
24. 12. 2008   #12
-
0
-

To o-lox : ináč to meranie rychlosti programu by ma zaujímalo ako robíš.. máš nejaký program,tool alebo niečo? a nie je to nahodou tak ze to zavisi od vykonnosti pocitaca?

Nahlásit jako SPAM
IP: 87.197.180.–
Mircosoft+1
Věrný člen
24. 12. 2008   #13
-
0
-

Rychlost výpočtů na rychlosti počítače pochopitelně závisí, časomíra se dá udělat tak, aby nezávisela - buď standardními funkcemi Getdate a Gettime (přesnost na setinu vteřiny) nebo vlastními prostředky přes přerušení časovače (např. http://mircosoft.ic.cz/download/CAS.PAS).

Nahlásit jako SPAM
IP: 85.132.158.–
Chceš-li lepší odpověď, polož lepší otázku.
Moje stránka.
o-lox0
Super člen
26. 12. 2008   #14
-
0
-

Používal jsem WinAPI - milisekundy, ne setiny. GetTickCount. A není nemožné ani pohrát si trochu s objektivností měření alespoň podle frekvence CPU - viz QueryPerformanceCounter. Pod DOSem pak assemblerem a čítačem časových značek, to ale nezohledňuje samozřejmě pipeline - architekturu.

Nahlásit jako SPAM
IP: 85.71.152.–
evandar0
Newbie
27. 12. 2008   #15
-
0
-

K tej Goldbachovej hypoteze ako takej.. myslim ze to uz len takym miernym zamyslenim sa vidiet ze vlastne samotna neplatnost tejto hypotezy je velmi vysoko nepravdepodobna, ked si vezmeme do uvahy ze prvocisla su vylucne neparne ( cesky liche ?? neviem :D ) a v intervale lubovolnych desat cisel ich byva 3-4 myslim a liche + liche = sude takze kombinacia by sa mala najst aj viac krat pri tych vyssich parnych ( sudych )

Ale aj ked je jej neplatnost velmi vysoka, to je asi dovod preco je to len hypoteza, platnost asi nikto nedokazal

Nahlásit jako SPAM
IP: 87.197.180.–
Krychlik
~ Anonymní uživatel
195 příspěvků
27. 12. 2008   #16
-
0
-

To evandar : To s 3-4 v 10 cislech neni pravda, prvocisla jsou stale vzacnejsi a vzacnejsi, milionte je okolo 150M a podle wiki je jich v 10E23 asi 1.9E21 tj v obou pripadech radove 1 v 100 cislech.

Nahlásit jako SPAM
IP: 212.111.4.–
evandar0
Newbie
27. 12. 2008   #17
-
0
-

To Krychlik : Fiha tak o prvocislach okolo 1000000+ som neuvazoval, ja skor do tej stovky max tsicky.. ale myslim ze pri tych vyskach okolo miliona tam je tolko moznych kombinacii ze aj 1 zo 100 staci ..

Nahlásit jako SPAM
IP: 87.197.180.–
Mishak070
Duch
3. 1. 2009   #18
-
0
-

Panove muzu vas vyrusit z akademicke diskuze? Prave tenhle priklad taky resim. Vsechno by fungovalo, ale mam problemy s casem. Jestli sem vsechno pochopil, jdou ty kroky po sobe takhle:
1. Eratosthenovo sito pro hodnoty 1 az 1000 000
2. Vytvoril sem si dalsi pole a do nej nacpal 78498 prvocisel (tolik jich je v milionu)
3. vsech nechal psat na sklo pomoci cyklu
while not seekeof do
begin
read(x);
if Sito[X] then writeln('Ouch!') else {tohle je z eratosthenova sita.. proste rve na prvocisla ouch :)}
begin
for i:=1 to 78498 do
begin
for j:=78498 downto i do
begin
Y:=prvo[i]+prvo[j];
if Y=X then begin writeln(X,'=',prvo[i],'+',prvo[j]); break end;
end;
if X=Y then break;
end;
end;
end;
Cyklus se seekeof je tam kvuli tomu, ze to vyhodnocuje aplikace a ja mam za to ze k ukonceni vraci prave eof. Nepomoh by mi to nekdo zrychlit? Aspon nejakej navrh.. diky

Nahlásit jako SPAM
IP: 88.101.44.–
o-lox0
Super člen
3. 1. 2009   #19
-
0
-

Já to udělal takto:
struct {int v,p;}vysl[10];

a=10; // mame jich 10 na vstupu v poli
for (i=0;i<prvocisel;i++)
for (j=prvocisel;j>i;j--)
{suma=(prvo[i]+prvo[j]);
for (b=0;b<a;b++){
if (suma==vstup)
{
vysl[vyslp].p=j;
vysl[vyslp++].v=vstup;
for (k=b;k<a-1;k++)
vstup[k]=vstup[k+1];
a--;
}
if (!a)
goto ven;
}
}

ven:

Nahlásit jako SPAM
IP: 85.71.152.–
o-lox0
Super člen
3. 1. 2009   #20
-
0
-

To o-lox : Zdá se mi to nebo se dneska zbláznilo uplně všechno....
A omlouvám se za jazyk C.
EDIT: delší dobu (ta necelá sekunda) mi trvá vytvoření prvočísel skrz erathostenovo síto, a pak využívám toho že hledám součet skrz pole pro všechny vstupy naráz.

Nahlásit jako SPAM
IP: 85.71.152.–
Mishak070
Duch
3. 1. 2009   #21
-
0
-

To o-lox : To C je v pohode.. sice moc nepobiram co je to v tom slozenym vyrazu (C uz sem nevidel dva roky :D), ale prived si me na myslenku s tim kombinovanim dvou prvocisel.. asi tozbytecne projizdim na dvakrat.. to by mozna mohlo pomoc.. :)

Nahlásit jako SPAM
IP: 88.101.44.–
Mishak070
Duch
3. 1. 2009   #22
-
0
-

To o-lox : Tak na to koukam.. Ty beres ze vstupu rovnou deset cisel? Zatim sem prisel jen na to ze sem zbytecne projizdel ty prvocisla, proste sem mel moc neefektivni sito.. Ale stejne se mi to nedari..

Nahlásit jako SPAM
IP: 88.101.44.–
o-lox0
Super člen
3. 1. 2009   #23
-
0
-

To Mishak07 : Nejrychlejc sestavený síto najdeš v pascalu na Wikipedii, jinak beru ze vstupu do pole všechny čísla co mám a v tom složenym bloku je jen to, že když jedno z těch čísel v poli ze vstupu je nalezeno, tak aby při dalšim hledání nezdržovalo, je odstraněno ze seznamu. Samozřejmě po tom co je "vyfotografovaný v souvislostech". Možná to jde ještě nějak vylepšit...

Nahlásit jako SPAM
IP: 85.71.152.–
Anonymní uživatel
~ Anonymní uživatel
0 příspěvků
1. 10. 2009   #24
-
0
-


Ke Goldbachvě hypotéze (dále GH)::

Uvedu tří další hypotézy.
Z platnosti těchto tří hypotéz
by vyplynula platnost GH.

1. Pokud sudé číslo splňuje GH,
pak buďto sudé číslo předchozí
nebo sudé číslo následující
nebo obě tato čísla také splňují GH.

Jinými slovy,
Pokud sudé číslo spňuje GH,
pak v jeho rozkladech do dvojic prvočísel
bude aspoň jedno (nebo více) prvočíslo
s vlastností, že číslo o dvě menší nebo
o dvě větší je opět prvočíslem.

2.Mějme sudé číslo splňující GH.
Nechť z jeho rozkladů do součtu prvočísel
není zaručeno, že následující sudé číslo
bude opět splňovat GH.ˇ(dále jen "nezaručuje dpředu")

(Žádné prvočíslo v jeho rozkladech
nemá tu vlastnost, že číslo o dvě větší je opět prvočíslem.
Je zajímavé, že nejmenší takové sudé číslo je 122.)

Pak další sudé číslo splňující GH
(ne nutně následující sudé číslo
může tam být mezera)
nezaručuje, že předchozí sudé číslo
bude spňovat GH (dále jen "nezaručuje zpět").

Jinými slovy, pokud sudé číslo spňující GH nezaručuje dopředu,
pak další sudé číslo spňující GH nezaručuje zpět.

3.Žádná mezera mezi "nezaručuje dopředu" a "nezaručuje zpět" není.

Jestliže někdo tzv. nabourá některou z těchto hypotéz, budu rád.
Mně se to zatím nepodařilo.

Nahlásit jako SPAM
IP: 83.208.187.–
sputnikone+1
Věrný člen
1. 10. 2009   #25
-
0
-

Nevytahujte tyhlety staré vlákna... po devíti mesících je to už trošku moc

Nahlásit jako SPAM
IP: 147.251.201.–
Anonymní uživatel
~ Anonymní uživatel
0 příspěvků
3. 10. 2009   #26
-
0
-

To sputnikone : Myslím, že nalezení důkazu pro Goldbachovu hypotézu
je i po devíti měsících stále aktuální.

Nahlásit jako SPAM
IP: 83.208.187.–
sputnikone+1
Věrný člen
3. 10. 2009   #27
-
0
-
Nahlásit jako SPAM
IP: 89.176.157.–
Yety0
Stálý člen
6. 10. 2009   #28
-
0
-

Anonymní uživatel napsal:
To sputnikone : Myslím, že nalezení důkazu pro Goldbachovu hypotézu
je i po devíti měsících stále aktuální.



Jj :)

Nahlásit jako SPAM
IP: 194.228.64.–
Kapitán A. J. Rimmer vesmírný dobrodruh
leco0
Newbie
3. 12. 2009   #29
-
0
-

Důkaz platnosti GH nemusí existovat.
Přesto nejspíš platí.
Nějaké vysvětlení proč by měla platit
existovat musí.

K 1. hypotéze:

Je možné, že existuje konečná množina
prvočísel složená z prvočíselných dvojčat
taková, že každý z rozkladů sudých čísel
do prvočíselných dvojic obsahuje aspoň jedno
prvočíslo z této množiny,

Nahlásit jako SPAM
IP: 83.208.187.–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 9 hostů

Podobná vlákna

Prosim pomoc — založil Honza

Prosim pomoc v c++ — založil miska

Prosím o pomoc — založil mergle

Pomoc prosim — založil Anonymní uživatel

Moderátoři diskuze

 

loadingtransparent (function() { var po = document.createElement('script'); po.type = 'text/javascript'; po.async = true; po.src = 'https://apis.google.com/js/plusone.js'; var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(po, s); })();
Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý