logi sisse meist KKK

Vaatleme arvutit, mille ainus mälu on pinu ja mille protsessori käsustikus on kaks operatsiooni:

  • DUP dubleerib pinu tipus oleva elemendi; see tähendab, viib pinu seisust [...,X| seisu [...,X,X|;
  • MUL asendab kaks pinu tipus olevat elementi nende korrutisega; see tähendab, viib pinu seisust [...,X,Y| seisu [...,X*Y|.

Kirjutada oma tavalise arvuti jaoks programm, mis saab positiivse täisarvu N ja väljastab käskude DUP ja MUL jada, mille täitmine sellel pinuarvutil asendab pinu tipmise elemendi X väärtusega X^N.

Eesmärk on muidugi optimeerida genereeritud koodi efektiivsust, kuigi generaatori efektiivsus tuleb ka ainult kasuks.

Näide: N = 4: DUP MUL DUP MUL, mille töö tulemus on [...,X|, [...,X,X|, [...,X^2], [...,X^2,X^2], [...,X^4].

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

küsitud Dec 07 '09 at 23:59

Ahto%20Truu's gravatar image

Ahto Truu ♦♦
6596711

Muidugi on astmenäitaja kahendesitusel põhinev lahendus igaks praktiliseks juhuks hea küllalt ja selle konstrueerimine on lisaks ka efektiivne ja kergesti mõistetav. Aga siiski pole see alati optimaalne. Näiteks N=15 korral annab see tulemuseks 12-käsulise jada DUP DUP MUL DUP DUP MUL DUP DUP MUL MUL MUL MUL, aga võimalik on ka 10-käsuline DUP DUP MUL MUL DUP DUP MUL DUP MUL MUL. Kes kirjutaks programmi, mis genereerib alati optimaalse koodi? Kes oskab põhjendada, et see väidetavalt optimaalne ongi parim võimalik?

(Dec 14 '09 at 21:44) Ahto Truu ♦♦

Mäletan, kui Ahto Ateena IOI-l pärast võistlust selle ülesande nuputamiseks andis. Minu leitud rekurrentne seos a[i]-de arvutamiseks oli eeltoodud Ahto lahendusest veidi kohmakam, aga see-eest leidsin viisi, kuidas optimaalse lahenduse otsimise asümptootilist ajakulu pisut vähendada. Pannes enda idee Ahto rekurrentsiga kokku, sain nüüd järgmise algoritmi.

const maxn = 1000000;
const leidmata = 'leidmata';
var a : array [1..maxn] of string;
var n, i, j : longint;
begin
   readln(n);
   a[1] := '';
   for i := 2 to n do
      a[i] := leidmata;
   for i := 2 to n do begin
      if (a[i] = leidmata) or (length(a[i]) > 8 + length(a[i - 1])) then
         a[i] := 'DUP ' + a[i - 1] + 'MUL ';
      for j := 2 to i do begin
         if i*j > n then
            break;
         if (a[i*j] = leidmata) or
                 (length(a[i*j]) > length(a[i]) + length(a[j])) then
            a[i*j] := a[i] + a[j];
      end
   end;
   writeln(a[n]);
end.

Põhimõtteliselt on siin Ahto algoritm lihtsalt "tagurpidi" pööratud: me ei hakka järjendit läbi vaatama mitte "ülevalt alla" (iga i jaoks tema tegureid läbi vaadates), vaid "alt üles" (kui saame mingi a[i] väärtuse lõplikult teada, siis uuendame ka i kordsete väärtusi), nagu Eratosthenese sõela puhul. Võit tuleb sellest, et "ülevalt alla" algoritm peab iga i jaoks läbi vaatama hulga arve j, mis ei ole i tegurid. Kui "ülevalt alla" algoritmi ajakulu on n*sqrt(n), siis "alt üles" algoritmi ajakulu on n*log(n).

Tõepoolest, iga i kohta tehakse vähem kui n div i sammu järgmiste a[i]-de uuendamiseks (sest i on teguriks ülimalt n div i arvule vahemikus 1...n), seega selliste sammude arv kokku ei ole suurem kui

n div 2 + n div 3 + n div 4 + ... + n div n < n(1/1 + 1/2 + 1/3 + ... + 1/n).

Sulgudes on harmoonilise rea osasumma, mis teadagi kasvab võrdeliselt n-i logaritmiga (selle nägemiseks võib nt. harmoonilise rea liikmeid lähendada kahe astmetega: 1 + 1/2 + 1/4 + 1/4 + 1/8 + 1/8 + 1/8 + 1/8 + 1/16 + ... < 1/1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + 1/9 + ... < 1/1 + 1/2 + 1/2 + 1/4 + 1/4 + 1/4 + 1/4 + 1/8 + 1/8 + ...). Nii saab ajakulu ka alt hinnata, nii et n*log(n) on täpne asümptootiline hinnang.

Kui nüüd jälle "ülevalt alla" vaatenurgale üle minna, siis selle ajahinnangu tõestamisega tõestasime järgmise tulemuse: arvude 1...N tegurite arvude summa on suurusjärgus N*log(N), s. t. arvul vahemikust 1...N on keskmiselt suurusjärgus log(N) tegurit.

Muidugi n*log(n) ajakulu on endiselt väga suur võrreldes väljundiga, mis on O(log n), nii et võib-olla on olemas kiirem algoritm optimaalse lahenduse leidmiseks.

link

vastatud Nov 05 '10 at 11:55

Jaan%20Vajakas's gravatar image

Jaan Vajakas
261

Järgnev Ruby-jupp leiab lühimad dupmul-jadad, kui sisend ei ületa väärtust 1037.

#### Data acquisition

$n = ARGV[0].to_i

#### Prime management

primep = [true] * ($n + 1)
primep[0 .. 2] = false, false, true
$primes = []

p = 2
while p * p < primep.length do
    if primep[p] then
        $primes.push p
        prod = p + p
        while prod < primep.length do
            primep[prod] = false
            prod += p
        end
    end
    p += 1
end

class Integer
    def each_factor_pair
        $primes.each do |f|
            yield f, self / f if self != f and self % f == 0
            return if f * f >= self
        end
        return
    end
end

#### Dynamic programming

def cache
    return Hash::new{|h,k| h[k] = yield k}
end

shortest_repr = cache do |arg|
    shortest_found = '(' + shortest_repr[arg - 1] + ')'
    arg.each_factor_pair do |f, g|
        candidate = shortest_repr[f] + shortest_repr[g]
        shortest_found = candidate if candidate.length < shortest_found.length
    end
    shortest_found
end

shortest_repr[1] = ''

#### User interface

words = {'(' => 'DUP', ')' => 'MUL'}
puts shortest_repr[$n].split('').map{|c| words[c]}.join(' ')

Mõnevõrra suuremate sisenditega saab majandada, kui enne väljundi genereerimist teha niimoodi:

(1 .. $n).each{|n| shortest_repr[n]}

Aga mis dünaamiline programmeerimine see siis enam on? Pealegi läheb suurte sisendite korral arvutamine aeglaseks:

tsume:tmp dig$ time ruby dupmul.rb 200000
DUP MUL DUP MUL DUP MUL DUP MUL DUP MUL DUP MUL DUP DUP MUL DUP MUL DUP DUP MUL DUP MUL DUP DUP MUL MUL DUP DUP MUL DUP MUL DUP MUL DUP MUL DUP MUL DUP MUL MUL MUL MUL

real    0m16.511s
user    0m16.371s
sys     0m0.074s

Reaalses maailmas võiks veel kaaluda mitmesuguseid ettearvutamise-lähenemisi. Näiteks on võimalik iga dupmul-jada pikkusega N kodeerida N + 1 bitiga; kui me jadad indekseerimise hõlbustamiseks oktabiti-piirini joondame, saame 64 kibibaidi sisse mahutada jadad kuni sisendini 14100. Veel on võimalik tulemuste asemel salvestada rekursiooniotsuseid. Kui me rekursiooniotsusena salvestame väiksema teguri või eriväärtuse 0 dekrementimise tähisena, saab 64 kibibaidi sisse mahutada rekursioonijadad kuni sisendini 65535. (Kuna väiksem tegur ei ületa kunagi ruutjuurt, mahub see 16-bitise sisendi korral 8 biti sisse. 0 ei ole kunagi väiksem tegur.)

link

vastatud Dec 21 '09 at 09:56

dig's gravatar image

dig
17415

... siis on veel see häda, et suurte sisendite korral võib pinuarvutil mälu ja/või pinupesabitid otsa saada. Samas, tont seda pinuarvutit teab, äkki ta hoiab tegelikult ainult astendajaid.

(Dec 21 '09 at 12:09) dig

Ma ei suutnud leida põhjendust, miks peaks olema piisav vaadelda ainult selliseid N tegurdusi, kus väiksem tegur on algarv. Tegin siis katse ja tuli välja, et näiteks N=1221 korral see ei olegi piisav...

(Jan 02 '10 at 00:32) Ahto Truu ♦♦

Kuna paistab, et selle ülesandega keegi enam ei tegele, käin välja oma lahenduse:

const maxn = 1000000;
var a : array [1..maxn] of string;
var n, i, j : longint;
begin
   readln(n);
   a[1] := '';
   for i := 2 to n do begin
      { a[i] algväärtus vastab esitusele X^i = X*X^(i-1) }
      a[i] := 'DUP ' + a[i - 1] + 'MUL ';
      for j := 2 to i do begin
         if j * j > i then begin
            break;
         end;
         if i mod j = 0 then begin
            if length(a[i]) > length(a[j]) + length(a[i div j]) then begin
               { a[i] uus väärtus vastab esitusele X^i = X^j^(i/j)) }
               a[i] := a[j] + a[i div j];
            end;
         end;
      end;
   end;
   writeln(a[n]);
end.

Põhjenduseks, miks see algoritm alati optimaalse lahenduse leiab, paneme tähele, et pinuprotsessori käsustikus pole mingit võimalust pääseda magasinis sügavamal olevate elementide kallale, alati saab toimetada ainult tipmise elemendiga. See tähendab, et X^i arvutus mistahes i>1 jaoks on võimalik ainult kahel viisil:

Esiteks me võime alguses dubleerida esialgse X, tõsta magasini tipus oleva uue koopia mingil viisil astmesse i-1 ja siis viimase sammuna need kaks väärtust kokku korrutada. See võimalus vastab eeltoodud programmis a[i] algväärtustamisele.

Teiseks me võime alustada sellest, et tõstame esialgse X kohe mingisse astmesse j, ehk asendame X väärtusega X^j. Kuna me sellega oleme esialgse X väärtuse kaotanud, saame edasi astendada ainult uut väärtust, mis tähendab, et X^i saamiseks peame selle avaldama kujul X^j^(i/j). Järjestikuste korrutamistega on seda võimalik teha ainult siis, kui mõlemad astmenäitajad on täisarvud, ehk ainult siis kui j on i tegur. See võimalus vastab eeltoodud programmis a[i] muutmisele.

Kuna eeltoodud programm need võimalused X^i saamiseks ammendavalt läbi vaatab ja muid võimalusi ei ole, peab leitav lahendus olema optimaalne. On üsna tõenäoline, et seda optimaalset lahendust saaks leida ka efektiivsemalt kui kõigi potentsiaalsete tegurite läbivaatus (mõelge kõigi nende kavalate algoritmide peale, mis on arvude tegurdamiseks välja mõeldud RSA ründamise käigus). Siiski muudaks see ainult pinuarvutile koodi genereerimise efektiivsust, aga mitte genereeritava koodi pikkust.

Omaette uurimisteema saame, kui hakkame mõtlema sellele, et X^1000000 on juba üsna väikese X korral väga suur arv ja tõenäoliselt sõltub ka vahetulemuste korrutamise töömaht sellest, kui suured on tegurid. Seda arvestades võib juhtuda, et reaalse pinuarvuti peal ei olegi minimaalse korrutamiste arvuga lahendus kõige kiirem (ja üsna tõenäoliselt juhtub, et kui minimaalse korrutamiste arvuga lahendusi on mitu, siis need ei ole kõik võrdse kiirusega). Selle teemaga tegelemiseks tuleks kõigepealt välja uurida (või hüpoteetilise masina korral kokku leppida), kuidas korrutamistehte ajakulu tema tegurite suurusest sõltub. Kuna seda ülesandepüstituses ei olnud, jääb see ka lahendusest välja.

link

vastatud Jan 07 '10 at 23:36

Ahto%20Truu's gravatar image

Ahto Truu ♦♦
6596711

Jõudsin sisuliselt sama lahenduseni kui einz, aga algoritm on iteratiivne ilma stackita.

procedure GenerateCode(N: Int64);
var
  Counter: Integer;
begin
  Counter := 0;
  while N > 1 do begin
    if Odd(N) then begin
      Inc(Counter);
      Writeln('DUP');
    end;
    Writeln('DUP', sLineBreak, 'MUL');
    N := N shr 1;
  end;

  while Counter > 0 do begin
    Writeln('MUL');
    Dec(Counter);
  end;
end;

EDIT: #10#13 -> sLineBreak

link

vastatud Dec 08 '09 at 14:22

Avo's gravatar image

Avo
12014

edited Dec 13 '09 at 17:36

2

Ei saa jätta norimata, et Writeln('DUP'#13#10'MUL'); asemel oleks parem Writeln('DUP'); Writeln('MUL'); -- mitte kõigil platvormidel pole reavahetus CR+LF.

(Dec 12 '09 at 22:43) Ahto Truu ♦♦

Selline oleks minu lahendus. Kasutab ära põhimõtteliselt N-i kahendesitust.

#include <iostream>
#include <cstring>
using namespace std;

void power(unsigned N)
{
    if (N > 1)
    {
    	// Kui viimane bitt on 1, kopeerime arvu.
    	if (N & 1) cout << "DUP ";
    	// Võtame pinu viimase arvu ruutu.
    	cout << "DUP MUL ";
    	// Vaatame järgmist bitti.
    	power(N >> 1);
    	// Kui arv oli kopeeritud, korrutame sellega.
    	if (N & 1) cout << "MUL ";
    }
}

int main (int argc, char * const argv[])
{
    if (argc > 1)
    {
    	power(atoi(argv[1]));
    	cout << endl;
    }
}
link

vastatud Dec 08 '09 at 13:23

einz's gravatar image

einz
213

millegipärast tekkis tunne, et algarv on segamini aetud naturaalarvuga

link

vastatud Dec 18 '09 at 17:34

erti%202's gravatar image

erti 2
71347

Lisan siis ka teise lahenduse mis töötab arvu tegurdamisel algalarvudeks. See lahendus peaks olema optimaalne.

Aste tegurdatakse algalarvudeks ja arv tõstetakse järjest neisse astmetesse (Arvu järjest astendamine on võrdne arvu astendamisega nende astmete korrutisega). Vaatleme igat algarvu tõsmist kui mingi pinus oleva arvu iseseisvat astendamist, kuna see tehe ei sõltu sellest mis astmes algne arv on või mis astmesse me tulemuse võtame. Kui arvu algalarvulisse astmesse tõstmine oleks optimaalselt lahendatud, siis oleks ka antud lahendus optimaalne.

Arvu algarvulisse astmesse tõstmine on lahendame järgmiselt:

Kui tegu on algarvulise kahest erineva astmega N vaatleme arvu astmesse N võtmist kui arvu korrutamiseks iseendaga astmes N - 1. Mingi arvu algalarvulisse kahest erinevasse astmesse tõstmiseks antud ülesandes peab vähemalt üks teguritest olema üks, et lõplik aste oleks paaritu, järelikult on tegu vajaliku ja seega optimaalse tehtega. Arvu võtame astmesse N - 1 rekursiivselt sama moodi nagu eelpool kirjeldatud. Rekursioon lõppeb, kui arvu on vaja võtta ruutu, mis tähendab tehetepaari "DUP MUL" ja on optimaalne. Kuna arvu algalarvu tõstmine on lahendatud ainult optimaalsete tehetega, on ka terviklahendus optimaalne.

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
// Arvu tegurdamine.
int factor(int N) {
    if (N % 2 == 0) return 2;
    for (int i = sqrt(N); i > 0; i -= 2) {
    	if (N % i == 0) return i;
    }
    return 1;
}
void power(int N) {
    if (N == 2) {			// 2 Korral võtame lihtsalt ruutu.
    	cout << "DUP MUL ";
    } else if (N > 1) {
    	int f = factor(N);	// Tegurdame astme
    	if (f == 1) {		// Kui aste on algalarv
    		cout << "DUP ";	// Lahutame astme arvu 1 ja mingi muu arvu summaks.
    		power(N - 1);	// Astendame ülejäänud osa
    		cout << "MUL ";
    	} else {
    		power(N/f);		// Võtame arvu astmesse esimene tegur.
    		power(f);		// Võtame tulemuse astmesse teine tegur.
    	}
    }
}
int main (int argc, char * const argv[]) {
    if (argc > 1) {
    	power(atoi(argv[1]));
    	cout << endl;
    }
}
link

vastatud Dec 18 '09 at 14:55

einz's gravatar image

einz
213

edited Dec 18 '09 at 20:55

Parandasin erti mainitud vea, naturaalarvu ajasin tõesti algarvuga segi.

(Dec 18 '09 at 20:56) einz

Esiteks, funktsioonis power on if (N == 2) eraldi käsitlemine mõttetu. Peaks olema üsna lihtne näha, et selle väljalõikamisel tulemus ei muutu: N=2 korral väljastatakse DUP MUL ja nende kahe vahel tehakse rekursiivne pöördumine power(1) poole, mis ei tee midagi.

(Dec 20 '09 at 21:43) Ahto Truu ♦♦

Teiseks, tundub, et mõte on olnud, et factor(N) tagastab N suurima algarvulise teguri, aga alati ta seda ei tee. Mõnikord võib juhtuda, et tagastatakse mittealgarvuline tegur (millest selles programmis ei juhtu küll midagi halba, aga mis selle funktsiooni kopeerimisel mingisse teise programmi võib anda ootamatu tagasilöögi) ja mõnikord võib juhtuda, et kordarvu puhul tagastatakse 1. Näiteks factor(21) korral nii lähebki.

(Dec 20 '09 at 21:44) Ahto Truu ♦♦
1

Kolmandaks, selle programmi aluseks olev idee pole õige. Näiteks N=33 korral leiab kahendesitusel põhinev lahendus 12 tehtega, aga selline agar tegurdaja 14 tehtega avaldise.

(Dec 20 '09 at 21:47) Ahto Truu ♦♦

See lahendus ei ole optimaalne, kuna ta üritab sisendit ainult tegurdada. Eksisteerib N=pq väärtusi, kus cost(seq(pq - 1)) + 1 < cost(seq(p) + seq(q)). Võib isegi juhtuda, et nende taga on mingisugune ilus seaduspärasus. (Tähistused: seq mäpib täisarvu lühimaks DUPMUL-jadaks, cost mäpib DUPMUL-jada selles leiduvate DUPMUL-paaride arvuks ehk pooleks jada pikkusest.)

(Dec 21 '09 at 12:16) dig
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: Dec 07 '09 at 23:59

nähtud: 4,603 korda

viimati uuendatud: Nov 05 '10 at 11:55

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