logi sisse meist KKK

Ülesanne: kirjutada programm, mis väljastab kõik 0 ja 1 vahele jäävad taandumatud murrud, mille nimetaja ei ületa etteantud täisarvu N.

Näide: N=2 --> 0/1, 1/2, 1/1.

Näide: N=3 --> 0/1, 1/3, 1/2, 2/3, 1/1.

PS. See on meelelahutus, mitte küsimus, mille vastust mulle millekski tegelikult vaja oleks.

[2009-11-03 01:40]

Teeme ülesande natuke raskemaks: murrud tuleb väljastada väärtuste kasvamise järjekorras, nagu näha ka eeltoodud näidetes.

küsitud Oct 31 '09 at 20:13

Ahto%20Truu's gravatar image

Ahto Truu ♦♦
6596711

edited Nov 02 '09 at 23:42


Olgu kolm järjestikust murdu on l1/n1, l2/n2, l3/n3, siis

l2 / n2 = (l1 + l3) / (n1 + n3) seega

l2 * k = l1 + l3 => l3 = l2 * k - l1 ja n2 * k = n1 + n3 => n3 = n2 * k - n1.

Kuna n3 <= n, siis n2 * k <= n1 + n => k = (n1 + n) div n2.

Seega, teades l1, n1, l2, n2, n saame arvutada l3 ja n3 vastavalt

l3 = l2 * (n1 + n) div n2 - l1 ja n3 = n2 * (n1 + n) div n2 - n1.

Et selles jadas on kaks esimest murdu alati 0/1 ja 1/n, siis ülejäänud saame välja arvutada.

Kood:

begin
  N := StrToInt(ParamStr(1));
  L1 := 0; N1 := 1;
  L2 := 1; N2 := N;
  Write('0/1 ');
  while L2 < N2 do begin
    Write(L2, '/', N2, ' ');
    K := (N + N1) div N2;
    L3 := K * L2 - L1; N3 := K * N2 - N1;
    L1 := L2; N1 := N2;
    L2 := L3; N2 := N3;
  end;
  Writeln('1/1');
end.
link

vastatud Nov 03 '09 at 08:13

Avo's gravatar image

Avo
12014

edited Nov 03 '09 at 08:31

Vau! Ma pole veel päris aru saanud kuidas see töötab. Aga see kahtlemata töötab lausa fantastiliselt.

(Nov 03 '09 at 21:53) Rene Saarsoo ♦♦
1

Üks võimalik alguspunkt lugemiseks: http://en.wikipedia.org/wiki/Farey_sequence

(Nov 29 '09 at 16:25) Ahto Truu ♦♦

Kuna seni pakutud lahendused kipuvad kõik n.ö. ühe võrra eksima, ehk siis kas 0/1 või 1/1 tulemusest välja jätma, siis siinkohal ka minu lahendus, mis peaks toda viga vältima.

Natuke Haskelli siis:

import Data.List
import System( getArgs )

-- x jagub y-ga kui jääk on 0
jagub x y = x `mod` y == 0

-- Murru taandamine.
-- Kui nii lugeja kui nimetaja jaguvad sama arvuga,
-- siis jagame ning proovime saadud murdu uuesti lihtsustada.
-- Teatud baasjuhtudel on vastus teada.
taanda (lug,nim) = taanda' (lug,nim) (min lug nim)
    where
    taanda' (0,nim)   _ = (0,1)
    taanda' (lug,nim) 0 = (lug,nim)
    taanda' (lug,nim) 1 = (lug,nim)
    taanda' (lug,nim) x =
        if lug `jagub` x && nim `jagub` x
            then taanda' (lug `div` x, nim `div` x) (x-1)
            else taanda' (lug, nim) (x-1)

-- Genereerib kõik 0..1 vahele jäävad taandamatud murrud
-- kus nimetaja <= n.  Eemaldab duplikaadid.
murrud n = nub [taanda (x,y) | x <- [0..n], y <- [0..n], x <= y]

-- Et saaks käsurealt käivitada
main = do
    args <- getArgs
    print $ murrud (head (map (\x -> read x::Int) args))

Võrreldes eelnevate lahendustega on see tigu-aeglane :)

TÄIENDUS: Ahto Truu soovituste abiga sai jõutud nüüd praktiliselt üherealise koodini, mis ühtlasi ka oluliselt kiirem (gcd leiab suurima ühisteguri):

murrud n = [(x,y) | x <- [0..n], y <- [0..n], x <= y, (x==0 && y==0) || gcd x y == 1]
link

vastatud Nov 02 '09 at 21:39

Rene%20Saarsoo's gravatar image

Rene Saarsoo ♦♦
1.1k101121

edited Nov 03 '09 at 20:37

1

Mu esimene mõte oli, et selle lahenduse aegluse põhjustab taandamisfunktsioon, mille saaks kirjutada efektiivsemalt umbes nii: taanda (lug,nim) = (lug div d, nim div d) where d = syt lug nim where syt 0 0 = 1 syt a 0 = a syt 0 b = b syt a b = gcd b (a mod b)

(Nov 02 '09 at 23:06) Ahto Truu ♦♦

Aga väike loomkatse näitas, et sellest pole suurt tolku, aeg läheb ilmselt kuhugi mujale. Siis mõtlesin, et kui juba syt olemas on, siis jätame kohe need välja, mis pole taandatud, ehk siis panna murrud n = nub [taanda (x,y) | x <- [0..n], y <- [0..n], x <= y] asemel murrud n = nub [taanda (x,y) | x <- [0..n], y <- [0..n], x <= y, syt x y == 1]

(Nov 02 '09 at 23:11) Ahto Truu ♦♦

Ei läinud eriti paremaks. Aga nüüd muidugi on (x,y) juba niigi unikaalsed ja järelikult pole nub enam vaja. Selle väljavõtmisega kukkus küll tööajalt mitu nulli ära.

(Nov 02 '09 at 23:14) Ahto Truu ♦♦

Vau, poleks osanud arvatagi, et Haskelli on sisse ehitatud suurima ühisteguri leidmise funktsioon. Seda ära kasutades muutub see ülesanne pea triviaalseks :)

(Nov 03 '09 at 20:39) Rene Saarsoo ♦♦

Haskelli üherealine versioon rokib :)

(Nov 04 '09 at 09:24) Tambet Matiisen ♦♦

Eeldusel, et nimetaja ei tohi ületada N-i, pakuksin sellise lahenduse:

#!/usr/bin/perl

my $n = $ARGV[0];
$n =~ /\D/ && die "Ainult täisarvud, palun";

my @vaartused = (0..$n);
my @murrud, %murru_arvestus;

foreach my $nimetaja (@vaartused) {
    !$nimetaja && next;
    foreach my $lugeja (@vaartused) {
    	if ($nimetaja > $lugeja && !$murru_arvestus{$lugeja/$nimetaja}) {
    		$murru_arvestus{$lugeja/$nimetaja}++;
    		push(@murrud, "$lugeja/$nimetaja");
    	}
    }
}

print "@murrud\n";
link

vastatud Oct 31 '09 at 23:47

WK's gravatar image

WK
893712

Ma näen selle lahenduse juures kaht kohta norimiseks:

1) kui ma Perli tüübisüsteemist väga valesti aru pole saanud, on $lugeja/$nimetaja ujukomaarv; nendega on alati risk, et ümardamisvea tõttu võib arvuti kaks matemaatiliselt võrdset suurust erinevateks lugeda (tõsi küll n=1000 korral veel sellist viga ei tekkinud);

2) töö ajal hoitakse kõiki murde mälus, mis pole tegelikult vajalik.

(Nov 02 '09 at 22:08) Ahto Truu ♦♦

Ahtole: 1) Jah, on ujukoma, ma mõtlesin sellele probleemile ja ei näinud põhjust, miks selline viga peaks tekkima. Mis ei tähenda, et ei või tekkida. 2) Eelistasin tulemuse puhverdada, vajadusel saab siis lisaoperatsioone (vormindada, näiteks) teha. Ülesanne seda muidugi ei nõua.

Renele: Kui ülesande tekst ütleb, et 0 ja 1 vahel, siis see nagu välistaks mõlemad. Näidetes olid jälle sees. Seega, pool tera.

(Nov 03 '09 at 00:22) WK

Uutele tingimustele kohandet lahendus:

#!/usr/bin/perl

my $n = $ARGV[0];
$n =~ /\D/ && die "Ainult täisarvud, palun";

my (@murrud, %murru_arvestus);

foreach my $nimetaja (1..$n) {
    foreach my $lugeja (0..($nimetaja-1) ) {
    	if (!$murru_arvestus{$lugeja/$nimetaja}) {
    		$murru_arvestus{$lugeja/$nimetaja} = "$lugeja/$nimetaja";
    	}
    }
}

@murrud = map {$murru_arvestus{$_}} (sort keys %murru_arvestus);
print "@murrud\n";
link

vastatud Nov 03 '09 at 01:00

WK's gravatar image

WK
893712

Üherealine Haskelli lahendus oli elegantne. Kindlasti teistes keeltes oleks samuti ilusam lahendus, kui gcd (greatest common divider) funktsioon sama lihtsasti ligipääsetav oleks.

Igal heal keelel on mingi library olemas, et ei peaks ratast leiutama hakkama. Antud probleem polnud niivõrd keerukas ja gcd tegi lahenduse triviaalseks. Teised lahendused ei "kuritarvitanud" ära mõnda juba olemasolevat funktsiooni, mis lahendamise väga lihtsaks teeb. Et teiste lahenduste suhtes ausam olla ja Haskelli lahendusse natuke pinget tagasi tuua, pakun välja, et lisaks lahendusse custom gcd implementatsiooni. Jah, see on reinventing the wheel, aga muidu on ju liiga lihtne :) Nuputamisülesande teeb just huvitavaks see, kui suuremosa heavy liftingust tuleb ise välja mõelda ;)

Seega lisan ühe võimaliku Haskelli gcd implementatsiooni:

myGcd :: Integral a => a ->  a ->  a  
myGcd 0 b = b  
myGcd a 0 = a  
myGcd a b = divide a b (min a b)  
            where  
              divide a b d | isModZero a d && isModZero b d = abs d  
                           | otherwise                      = divide a b (d-1)  
              isModZero x y | x `mod` y == 0 = True  
                            | otherwise      = False

Well, implementastioonil veel paranemisruumi on kui võrrelda seda Prelude gcd-ga:

*Main> :set +s  
*Main> gcd 10230 20410  
10  
(0.05 secs, 3573488 bytes)  
*Main> myGcd 10230 20410  
10  
(0.09 secs, 4388252 bytes)
link

vastatud Nov 29 '09 at 19:18

Innar%20Made's gravatar image

Innar Made
112

Rene Haskelli-versiooni kommentaarides oli juba olemas suurima ühisteguri arvutamine Eukleidese algoritmiga, mis on nii lühem kirja panna kui ka arvutil kiirem täita (kommentaari pandud kood näeb küll üsna kole välja, sest reavahetused süüakse ära, panen nende asemel komad): syt 0 0 = 1, syt a 0 = a, syt 0 b = b, syt a b = gcd b (a mod b)

(Nov 29 '09 at 23:33) Ahto Truu ♦♦
Sinu vastus
lülita eelvaade

Jälgi seda küsimust

By Email:

Pärast sisselogimist saad tellida muudatuse teavitusi siit

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *kaldkiri* või __kaldkiri__
  • **paks kiri** või __paks kiri__
  • link:[tekst](http://url.com/ "pealkiri")
  • pilt?![alt tekst](/path/img.jpg "pealkiri")
  • nummerdatud nimekiri: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • põhilised HTML märgendid on samuti toetatud

Pinu tööpakkumised

kõik pakkumised »

Küsimuse sildid:

×7

küsitud: Oct 31 '09 at 20:13

nähtud: 3,710 korda

viimati uuendatud: Nov 29 '09 at 19:18

Litsents: Creative Commons Attribution License | Kontakt: info@pinu.ee