Dotaz: Nalezení všech dělitelů čísla C++

[Hlavson]

Ahoj všichni. Potřeboval bych vyrobit algoritmus na zjištění všech dělitelů zadného čísla... Pokud máte nějaké nápady, sem s tím.

Např. číslo 10 ... (10/5/2/1)

Děkuju moc.

Odpovědi

[jirkamailto]

Nevim jak to chces, ale primarne budes zjistovat zbytky po deleni, tak ja bych to resil forcyklem od 1 do cisla, ktere mas zadane a iteroval bych po 1. Dale pokud by byl zbytek po deleni 0, tak bych cislo, ktere je v iteraci aktualni, nasypal do pole nebo vypsal na obrazovku, jak chces. Pote nakonec bych to pole prosel a vypsal vsechny jeho prvky.

[Dejv]

forcyklem od 1 do cisla, ktere mas zadane

Zbytecne dlouhe. Staci od 2 (kazde cislo je delitelne 1 a samo sebou) do SQRT(cislo) (do druhe odmocniny - SQRT(cislo) * SQRT(cislo)= cislo) a ukladat delitele i vysledek.

Dejv

[mess]

Nejprve bych si našel všechna prvočísla do např. 10 (pokud hledáš dělitele 10) - viz Erathostenovo síto. Až budeš mít ta prvočísla, tak je ber od největšího a zkoušej celočíselné dělení.

[pht]

Prvočísla to jen zkomplikují.

[Tomáš]

Nikoliv prvočísla jsou klíčem. Protože pokud se vám číslo N podaří rozložit na prvočísla a_i, v následující notaci:

N= a_1 × a_2 × ...;

Pak každá vlastní podmnožina množiny s prvky a_i odpovídá právě jednomu děliteli.Hodnota dělitele je rovna součinu prvků této podmnožiny.

Postupoval bych tak, že bych získal na internetu zeznam prvočísel (pole P). Algoritmus by pak byl následující (neodladěný nástin algoritmu).

 

/* pole A - provočísla v N. pole B kardinalita prvočísla v rozkladu 
na začátku je pole B vynulováno*/
k=0;
l=0;
count=0;
while ( N > 1) {
 if N mod P[k] == 0 {
    A[l] = P[k];
    B[l]++;
    N=N/B[k];
    count++;
 } else {
    k++;
    if B[l]>0 {
      l++;
    }	
 }
}
/* V poli A máme rozklad na prvočísla. Ted jeste pronasobit. 
Místní validátor mrší kód a podruhé to psát nebudu.
Tak to budete muset vymyslet samostatně.*/

[Michal Kubeček]

Seznam prvočísel je zbytečný, stačí si vytvořit sezman prvočíselných dělitelů. Navíc zapomínáte na to, že N může být dělitelné i vyšší mocninou některého prvočísla. Takže začnu s p=2 a budu zkoušet dělitelnost. Když narazím na dělitele, zapíšu si ho do pomocné struktury a zjistím maximální mocninu p, která dělí N (a poznamenám si ji k tomu děliteli). N vydělím touto mocninou (to se udělá jako vedlejší produkt v průběhu jejího zjišťování) a pokračuji dál. Končím v okamžiku, kdy p^2 > N. Je-li v tu chvíli N>1, je to poslední prvočíselný dělitel.

Výsledkem je pole, kde mám prvočíselný rozklad (prvočísla p_i a mocniny a_i). Zbývá vygenerovat seznam dělitelů, což je ekvivalentní všem možnostem, jak jednotlivým prvočíslům p_i přiřadit mocniny od nuly do a[i]. To už si laskavý čtenář udělá za cvičení, aby si ten zápočet aspoň nějak zasloužil. :-)

Technická poznámka: pokud by to náhodou nebyl úkol a ten program se měl použít v praxi, tak takhle komplikovaně to má smysl dělat jen pro velká N, pro menší je daleko jednodušší (a nezřídka i rychlejší) použít nějaký hrubonásilný přístup.

[pht]

Ve výsledku stejně projdete čísla od 1 do sqrt(N), tak to už je pomalu jednodušší zkoušet dělit rovnou. Při jednoduchém cyklu dostanu pole dělitelů - výsledek, při testování prvočísel je ještě budu navíc muset netriviálně kombinovat.

[Michal Kubeček]

Jenže u mého algoritmu to N průběžně klesá. Když vezmu extrémní případ, pro N = 2^k dostanete výsledek v čase sqrt(N) = 2^(k-1), u mne to bude k = log_2 N. V opačném extrému (N je prvočíslo) na tom budeme oba stejně.

[Michal Kubeček]

Samozřejmě tam mělo být sqrt(N) = 2^(k/2), ale na principu to nic nemění.

[pht]

Jo, to je vlastně pravda.

[František Jahoda]

Příloha:

• dividers.py (1112 bytů)

algoritmus je opravdu pro cislo N slozene z vice prvocisel podstatne rychlejsi.
predpoklad N = product(i=1..k, p_i ^ alpha_i)

analyza prvocisel cca sqrt(N)
vycisleni ruznych permutaci product(i=1..k, alpha) << N odhadoval bych cca O( ln N )
vycisleni delitele pomoci permutace k

takze celkem bych ocekaval slozitost O(sqrt(N)). to bude plati i pro N prvocislo

[Radek Miček]

IMO lepší je čas. složitost udávat jako funkci závislou na délce vstupu

[kulik]

pouzij hlavu Hlavsone, toto je ukol zhruba tak pro ctvrtou tridu zakladni skoly

[Michal Kubeček]

Dovolím si tipnout, že to je domácí úkol, i když asi ne zrovna pro čtvrtou třídu ZŠ.

[kulik]

No na ten trivialni algoritmus "zkusim vsechna mensi cisla, zda jsou delitelem" by podle mne melo prijit i hodne male dite, urcite na prvnim stupni ZS. Omezeni na cisla <=  odmocnina bych videl tak na sestou tridu u deti co je zajima matematika, nejake vylepseni pres prvocinitele pak treba osma trida (bez dukazu slozitosti apod.). Samozrejme inplementace v C++ je neco jineho, ne kazdy zna C++, ale myslenkove to opravdu neni nic extra sloziteho. Narazel jsem puvodne hlavne na to, ze zakladni reseni by pravdepodobne bylo hotove v dobe zhruba srovnatelne s napsanim dotazu do poradny...

[Michal Kubeček]

Narazel jsem puvodne hlavne na to, ze zakladni reseni by pravdepodobne bylo hotove v dobe zhruba srovnatelne s napsanim dotazu do poradny...

Řekl bych, že toho, pro koho tohle platí, vůbec nenapadne sem takový dotaz dát. Dá-li ho sem někdo, pak to nejspíš bude ten, kdo tu úlohu není schopen vyřešit vůbec. Otázkou ovšem je, jestli je vhodné, aby takový člověk studoval školu, kde po něm podbné věci chtějí…

[Hlavson]

Tak tady to je....

 

prev>>a;

b=a;

    for(;b>0;b--)
    {
        if(a%b==0)
        {

vypis....

        }
    }

Asi nejsrozumitelnější řešení...

[Ash]

To jste napsal takový méně přehledný zápis

for(b=a; b<0; b--) {
  if(a%b == 0) {
    výpis
  }
}

no nic proti hrubé síle, když na to máte dost času...

[Ash]

prohozeno <>

[happy barney]

hmm, pýtať sa na jeden riadok (vygoogliteľný k tomu)

perl -le 'print for grep ! ($ARGV[0] % $_), 1 .. $ARGV[0]' 10000

[Michal Kubeček]

Ještě na tom bude potřeba zapracovat:

mike@unicorn:~/tmp> g++ -c x.cc
x.cc:1:10: warning: character constant too long for its type
x.cc:1: error: expected constructor, destructor, or type conversion before ‘-’ token

:-)

[pht]

Aneb klasický příklad toho, že hlášky překladačů C jsou úplně mimo.

[l4m4]

Zejména, když jim někdo předloží kód v perlu...

[Michal Kubeček]

A co by podle vás měl napsat? "Jsi blbec, tohle je perl!" ? :-)

[pht]

V podstatě ano. Porovnejte s:

$ cat x.adb
perl -le 'print for grep ! ($ARGV[0] % $_), 1 .. $ARGV[0]' 10000 
$ gnat make x 
gcc -c x.adb
x.adb:1:01: compilation unit expected
gnatmake: "x.adb" compilation error

[moira]

mike@unicorn?

To je skryta reklama nebo antireklama? :)))

[Michal Kubeček]

Proč reklama? To je prostě jméno počítače (druhý se jmenuje lion, třetí walrus a čtvrtý bude nejspíš carpenter :-) ). Ono dneska najít slovo, které by nebylo použito jako název nějaké firmy, je asi docela problém…

[Ash]

Koukam že C++ od mejch mladejch let nějak pokročilo :D

[asdf]

primitivne, v paskale, a bez zaruky:)

program delitel;

type
  TPole= array[0..0] of integer;
  PPole= ^TPole;

var
  n, i: integer;
  P: PPole;
  x: integer= 0;

begin
  read(n);
  GetMem(P, n*SizeOf(integer));
  
  for i:=1 to n do 
    if n mod i = 0 then 
     begin
       P^[x]:=1;
       inc(x);
     end; 
     
  for i:=0 to x do write(' ', P^[i]);

end;

[asdf]

teda P^[x]:=i;

[Radek Miček]

Pro prirozena cisla a v Haskellu :

delitele x = filter ((== 0) . mod x) [1..x]

[Michal Kubeček]

A co z toho plyne? Takhle "efektivně" to zvládnu i v tom C++:

  for (i=1;i<=N;i++) if (!(N%i)) s << i << "\n";

Dokonce i ta délka je přibližně stejná. Kdybych si pamatoval prioritu operátorů, možná bych ušetřil ještě dvě závorky.

[Radek Miček]

Takhle "efektivně" to zvládnu i v tom C++:

Já nikde netvrdím, že ne.

Mj. podívejte se na kód v Haskellu, je mnohem přehlednější než ten váš, protože používá standardní funkci (dalo by se říci: návrhový vzor) filter.

[Michal Kubeček]

je mnohem přehlednější než ten váš, protože používá standardní funkci (dalo by se říci: návrhový vzor) filter.

Tomuto argumentu nerozumím. Já snad v tom kódu používám něco nestandardního? Co se přehlednosti týká, zkuste si to upravit aspoň tak, abyste necyklil do N ale jen do odmocniny a hned se vám to trochu zkomplikuje. Kdyby mi šlo o přehlednost, zvolil bych samozřejmě jiné formátování.

Ale nenechte se odradit mou skepsí, já jsem prostě starý bručoun, který neochotně podléhá módním vlnám a bere s rezervou podobné ukázky toho, jak se v těch revolučních jazycích třeskutě elegantně (a často zoufale neefektivně) řeší pečlivě vybrané (a většinou velmi umělé) úlohy.

[Radek Miček]

Tou přehledností jsem měl na mysli spíše to, že v imperativních jazycích se zatím běžně používájí konstrukce for, if atd. Problém je, že tyto konstrukce jsou velmi obecné, zatímco ve funkcionálních jazycích se používají konstrukce s funkcemi map, filter, foldl, což jsou méně obecné konstrukce a osobně, když vidím třeba map f l, hned vím, že výsledekm je seznam stejně dlouhý jako seznam l a také vím, jaký typ mají prvky uvnitř seznamu (to určím z typu funkce f).

Jinak řečeno, když vidím standardní funkci map, filter anebo foldl, tak už tuším, co bude kód dělat. Zatímco, když vidím for cyklus, tak toho moc nevím. Mj. podobné věci se stále více objevují i v běžně používaných jazycích.

Nebojte, odradit se nenechám Ale uvažte, že tyto, jak říkáte módní jazyky, jsou zdrojem nových featur pro ty běžně používané jazyky. A možná i díky jazykům jako je Haskell se dočkáme rozšíření trochu pokročilejších typových systémů do běžné praxe.

[Radek Miček]

Podívejte se třeba, jak pěkně lze v Haskellu napsat parser pro escape sekvenci:

-- | Parses escape sequence.
escape :: Parsec String st Char
escape = backslash *> (p_char <|> p_num <|> p_any) <?> "escape sequence"
  where
    -- Parses single-character escape sequence (from table @chars@).
    p_char = lookup' chars <$> (oneOf . fst . unzip $ chars)
    -- Parses numeric escape sequence. Numeric escape sequence starts
    -- with @x@ or @u@.
    p_num = toEnum . fst . head . readHex
              <$> (try (oneOf "xu" >>
                        between (char '{') (char '}') (many1 hexDigit))
                     <|> char 'x' *> count 2 hexDigit
                     <|> char 'u' *> count 4 hexDigit)
    -- Parses other escape sequences.
    p_any = anyChar
    chars = zip escapeCodes escapeChars

[Michal Kubeček]

Někomu to sice možná připadá pěkné, ale zase to o kvalitě a praktické použitelnosti jazyka vůbec nic neříká. V takovém lexu to bude ještě jednodušší a ještě přehlednější, ale co z toho? Síla C a C++ je v jejich univerzalitě, ne v tom, že napíšu konkrétní šikovně vybranou úlohu o řádek kratšeji a a s hezčím zdrojákem, abych dělal dojem v diskusi.

[Radek Miček]

Ano, v lexu by toto bylo přehlednější a kratší. Ale lex/bison je nemodulární řešení -- já tento parser (nebo lexer, ale obecně s knihovnou Parsec mohu udělat parser LL gramatiky) mohu složit s jinými a poskládáním menších parserů mohu vytvořit jeden velký parser. Navíc s knihovnou Parsec mohu ovlivnit chybová hlášení, která parser zobrazí uživateli.

Síla C a C++ je v jejich univerzalitě, ne v tom, že napíšu konkrétní šikovně vybranou úlohu o řádek kratšeji a a s hezčím zdrojákem, abych dělal dojem v diskusi.

Haskell není jazyk zaměřený na jednu vybranou úlohu viz třeba HackageDB.

[Michal Kubeček]

Haskell není jazyk zaměřený na jednu vybranou úlohu viz třeba HackageDB.

Ale no tak… Předpokládám, že není nutné, abych to porovnával s tím, kolik knihoven a frameworků je k dispozici pro C a C++. Není vyloučeno, že časem Haskell dospěje do podoby jazyka pro široké spektrum uplatnění a že se bude opravdu široce používat. Ale zatím je podle mne jásání a předhazování Haskellu jako léku na neduhy C/C++ a budoucnosti programování předčasné. V tomhle jsem prostě skeptik. Zažil jsem vlny nadšení z Prologu, Lispu, Forthu, dnes je v módě Haskell, ale vždycky to byly a vždy to zůstaly spíš akademické záležitosti. Chlebem programátorského světa jsou už po desítky let procedurální jazyky a zatím mne nic nepřesvědčilo, že se to v dohledné době zásadním způsobem změní.

[Radek Miček]

Ten odkaz jsem dal proto, aby bylo vidět, že se v Haskellu řeší různorodé problémy.

[Radek Miček]

IMO funkcionální programování se stále více a více prosazuje, důkazem toho může být třeba F#, což je upravený OCaml. Já neříkám, že se bude programovat čistě funkcionálně (tj. tak jako v Haskellu), ale myslím si, že mnoho prvků z těchto jazyků se postupně objeví v mainstreamových jazycích.

[Ladicek]

Já asi chápu, o co kolegovi jde. Chlebem programátorského světa, jak tomu hezky říkáte , dnes nejsou procedurální jazyky, ale jazyky objektové. Jenže zatímco typové systémy procedurálních jazyků jsou dnes velmi pokročilé (Ada), typové systémy běžných objektových jazyků jsou prakticky zoufale impotentní. A s tím významně souvisí vyjadřovací schopnost těchto jazyků a produktivita jejich uživatelů. Proto se někteří lidé utíkají k funkcionálním jazykům. A je pravda, že některé jejich vlastnosti pomalu prosakují do mainstreamu (C#).

[Michal Kubeček]

nejsou procedurální jazyky, ale jazyky objektové

Pominu-li různé specialitky, není ve filosofii mezi klasickými procedurálními a objektově orientovanými jazyky zase až tak zásadní rozdíl. Tedy aspoň ne z pohledu diskuse, kde je na jedné straně C/C++ a na druhé Prolog, Lisp nebo Haskell.

[Sinuhet]

Na to mame v C++ spirit.

[Radek Miček]

Díky, je to docela pěkné.

Ale nevýhoda C++ je, že máte jen omezený počet operátorů s předem danými prioritami. Výhodou Haskellu je lazy evaluation. Mj. našel jsem sbírku podobných knihoven jako je Parsec.

[Radek Miček]

A dovolím si ještě jednu poznámku. Kdyby nebylo takovýchto jazyků, tak bychom třeba ani neuměli derivovat datové struktury nebo bychom pro to neměli praktické uplatnění.

[Michal Kubeček]

nebo bychom pro to neměli praktické uplatnění.

Jinak řečeno: nebýt takových jazyků, neuměli bychom to, ale bylo by nám to jedno, protože bychom to vlastně ani nepotřebovali. :-)

[Michal Kubeček]

Ta předchozí odpověď byla samozřejmě myšlena jako vtip, ale propagátoři těch módních jazyků si o to sami říkají tím, jak jejich přednosti v mnoha případech demonstrují na umělých úlohách, které jsou okatě vymýšleny právě za tím účelem, aby v daném jazyce šly řešit elegantně. Jenže s takovými úlohami se programátor v běžné praxi setkává jen zřídka.

[Ivan]

Hledej na google: quadratic sieve, Kod urcite nebude tak elegantni jako jedna radka v haskelu, ale rozhodne to bude "pouzitelnejsi".