RSS

Klub Mistrzów Komputera trzydzieści lat później: jedynki i zera

Liczba odsłon: 173

po­przed­nim wpi­sie blo­gu za­mieś­ci­łem roz­wią­za­nie za­da­nia „Klubu Mistrzów Komputera” cza­so­pis­ma Komputer sprzed trzy­dzie­stu lat. Dzisiaj roz­pa­tru­ję – do te­go na dwa spo­so­by – ko­lej­ną za­gad­kę pro­gra­mi­stycz­ną te­go klu­bu, o dwa la­ta młod­szą.

Oto treść za­da­nia, opu­bli­ko­wa­ne­gonu­me­rze 10/1989 cza­so­pis­ma:

Łatwo moż­na udo­wod­nić, że dla każ­dej licz­by na­tu­ral­nej k ist­nie­je licz­ba zło­żo­na tyl­ko z zer i je­dy­nek (w za­pi­sie dzie­sięt­nym) bę­dą­ca wie­lo­krot­no­ścią licz­by k.

Proponu­ję na­pi­sać pro­gram znaj­du­ją­cy ta­ką licz­bę dla da­nej licz­by k.

Podobnie jak po­przed­nio, do roz­wią­za­nia za­da­nia wy­ko­rzy­sta­my ję­zyk Java­Script, choć tym ra­zem nie bę­dą nam po­trzeb­ne żad­ne je­go spe­cy­ficz­ne ce­chy. Jego za­sto­so­wa­nie po­zwo­li jed­nak stwo­rzyć roz­wią­za­nie w po­sta­ci apli­kac­ji sie­cio­wej i ogra­ni­czyć do mi­ni­mum na­kład pra­cy po­trzeb­nej do stwo­rze­nia przy­zwoite­go inter­fej­su użyt­kow­ni­ka. Ponadto, ję­zyk Java­Script ma wiel­ką za­le­tę z punk­tu wi­dze­nia dy­dak­ty­ki: każ­dy mo­że uru­cho­mić, prze­ana­li­zo­wać i zmo­dy­fi­ko­wać przy­kła­do­we pro­gra­my bez ko­niecz­noś­ci in­sta­lo­wa­nia spe­cja­lis­tycz­nych na­rzę­dzi pro­gra­mis­tycz­nych.


Zacznijmy od wpro­wa­dze­nia da­nych wej­ścio­wych. Będzie do te­go słu­żył for­mu­larz HTML wy­ge­ne­ro­wa­ny na pod­sta­wie na­stę­pu­ją­ce­go ko­du:

<form>
 <fieldset>
  <label for="value">Liczba do przekształcenia:</label>
  <input id="value"/><br/>
  <label for="method">Metoda wyznaczania:</label>
  <select id="method">
  </select><br/>
  <button type="button" onclick="perform();">Przekształć</button>
 </fieldset>
</form>
<pre id="result"></pre>
<script type="text/javascript">
 document.getElementById('value').focus();
</script>

Wczyta­my za je­go po­mo­cą dwie pod­sta­wo­we in­for­mac­je:

Dodatkowo, po­ni­żej for­mu­la­rza znaj­du­je się miej­sce na wy­ni­ki dzia­ła­nia pro­gra­mu. Warto też pa­mię­tać o frag­men­cie ko­du wy­mu­sza­ją­cym umiesz­cze­nie ka­ret­ki w po­lu wpro­wa­dza­nia da­nych, co ułat­wi pra­cę użyt­kow­ni­ko­wi.

Właściwy wy­gląd for­mu­la­rza za­pew­ni na­stę­pu­ją­cy frag­ment ar­ku­sza sty­lów CSS:

label {
 display: inline-block;
 text-align: right;
 width: 11em;
}
input {
 margin: 2pt;
}

Ponie­waż przy szu­ka­niu roz­wią­za­nia bę­dzie­my ope­ro­wać na licz­bach, nie jest po­trzeb­na de­kom­po­zy­cja obiek­to­wa przed­mio­tu prze­twa­rza­nia. Przewidu­je­my jed­nak moż­li­wość sto­so­wa­nia róż­nych me­tod reali­zac­ji obli­czeń, war­to za­tem za­mo­de­lo­wać obiek­to­wo hie­rar­chię sil­ni­ków obli­cze­nio­wych. Jeżeli do­dat­ko­wo w ba­zo­wej kla­sie sil­ni­ka obli­cze­nio­we­go za­wrze­my me­cha­nizm umoż­li­wia­ją­cy ob­ser­wo­wa­nie licz­by ite­ra­cji algo­ryt­mu oraz cza­su po­szu­ki­wa­nia roz­wią­za­nia, zy­ska­my moż­li­wość łat­we­go po­rów­ny­wa­nia po­szcze­gól­nych me­tod ze so­bą.

Klasę ba­zo­wą na­zwie­my Solver i na­da­my jej kon­struk­to­ro­wi na­stę­pu­ją­cą po­stać:

function Solver() {
   this.lengthLimit = 12;
   this.numIterations = 0;
}

Pole lengthLimit bę­dzie na­rzu­ca­ło li­mit dłu­goś­ci wy­ni­ku. Zapobieg­nie to zbyt dłu­gie­mu po­szu­ki­wa­niu wy­ni­ku bez po­trze­by lub wręcz za­wie­sza­niu się pro­gra­mu. Z kolei po­le numIterations bę­dzie po­zwa­la­ło od­czy­tać licz­bę zrea­li­zo­wa­nych ite­ra­cji.

Do na­rzu­ca­nia li­mi­tu dłu­goś­ci wy­ni­ku po­słu­ży nam na­stę­pu­ją­ca me­to­da:

Solver.prototype.setLengthLimit = function(limit) {
   if (typeof limit !== 'number' || limit < 2 || limit > 100)
      throw new Error('Invalid limit: ' + limit);
   this.lengthLimit = limit;
};

Zapobie­ga ona przy­pad­kom po­da­nia no­we­go li­mi­tu w po­sta­ci in­nej niż licz­ba lub spo­za za­kre­su, dla któ­re­go pro­wa­dze­nie obli­czeń jest moż­li­we i sen­sow­ne.

Z kolei do od­czy­ty­wa­nia licz­by ite­ra­cji i cza­su obli­czeń po­słu­żą na­stę­pu­ją­ce pros­te akce­so­ry:

Solver.prototype.getNumIterations = function() {
   return this.numIterations;
};

Solver.prototype.getDuration = function() {
   return this.timeEnd - this.timeStart;
};

Może nam się rów­nież przy­dać me­to­da we­ry­fi­ku­ją­ca, czy uzys­ka­ny wy­nik speł­nia wa­run­ki za­da­nia. Oto pro­po­zyc­ja tek­stu ta­kiej me­to­dy:

Solver.prototype.isValidResult = function(result) {
   if (typeof result === 'number')
      result = result.toString();
   else if (typeof result !== 'string')
      throw new Error('Invalid result: ' + result);
   var ch;
   for (var i = 0; i < result.length; ++i) {
      ch = result.charAt(i);
      if (ch !== '0' && ch !== '1') return false;
   }
   return true;
};

Nadszedł czas, by stwo­rzyć naj­waż­niej­szą me­to­dę, roz­po­czy­na­ją­cą po­szu­ki­wa­nie właś­ci­we­go wy­ni­ku. Klasa Solver nie reali­zu­je tych po­szu­ki­wań, za­tem me­to­da ta bę­dzie tyl­ko ini­cja­li­zo­wa­ła pro­ces i wy­wo­ły­wa­ła im­ple­men­tac­ję właś­ci­wą dla wska­za­ne­go sil­ni­ka obli­czeń. Będzie też od­po­wie­dzial­na za właś­ci­we zli­cza­nie cza­su prze­twa­rza­nia:

Solver.prototype.solve = function(value) {
   if (typeof value !== 'number' || value < 0)
      throw new Error('Invalid value: ' + value);
   if (value < 2) return 1;
   this.numIterations = 0;
   this.timeStart = performance.now();
   var result = this.solveInternal(value);
   this.timeEnd = performance.now();
   return result;
};

Teraz, gdy dy­spo­nu­je­my już pod­sta­wą sil­ni­ka obli­cze­nio­we­go, za­pisz­my im­ple­men­tac­ję pierw­sze­go z nich. Dzięki wy­łą­cze­niu pod­sta­wo­wych, wspól­nych dla wszyst­kich me­tod funkcjo­nal­noś­ci w kla­sie ba­zo­wej Solver, po­szcze­gól­ne im­ple­men­tac­je bę­dą prost­sze, krót­sze i bar­dziej czy­tel­ne. Znów zacz­nie­my od me­to­dy brute force, mno­żąc licz­bę przez ko­lej­ne wie­lo­krot­no­ści aż do mo­men­tu zna­le­zie­nia roz­wią­za­nia lub prze­kro­cze­nia li­mi­tu dłu­goś­ci wy­ni­ku:

function BruteForceSolver() {
   Solver.call(this);
}

BruteForceSolver.prototype = Object.create(Solver.prototype);

BruteForceSolver.prototype.solveInternal = function(value) {
   var result, resultStr;
   for (var i = 1;; ++i) {
      this.numIterations++;
      result = value * i;
      resultStr = result.toString();
      if (resultStr.length > this.lengthLimit) return false;
      if (this.isValidResult(resultStr)) return i;
   }
};

Aby moż­li­we by­ło uru­cho­mie­nie obli­czeń, na­le­ży do­dać do for­mu­la­rza po­zyc­ję poz­wa­la­ją­cą wska­zać no­wo za­pi­sa­ny sil­nik obli­cze­nio­wy:

<select id="method">
 <option value="BruteForceSolver">brute force</option>
</select><br/>

oraz za­pi­sać funk­cję uru­cha­mia­ją­cą obli­cze­nia:

function perform() {
   var value = parseInt(document.getElementById('value').value);
   var method = document.getElementById('method').value;
   var solverFn = window[method];
   var solver = new solverFn();
   var result = solver.solve(value);
   var resultField = document.getElementById('result');
   var resultText;
   if (result === false) resultText = 'brak rozwiązania';
   else resultText = value + ' × ' + result + ' = '
                              + (value * result);
   resultText += '<br/>Liczba iteracji: ' + solver.getNumIterations();
   resultText += '<br/>  Czas obliczeń: ' + solver.getDuration() + ' s';
   resultField.innerHTML = resultText;
}

W tym mo­men­cie for­mu­larz po­wi­nien „ożyć” i za­cząć rea­go­wać na wpro­wa­dza­ne da­ne.

Progra­mo­wa­nie (szcze­gól­nie zorien­to­wa­ne obiek­to­wo) ma tę przy­jem­ną ce­chę, że prze­my­śla­ny szkie­let apli­kac­ji, choć pra­co­chłon­ny, dia­met­ral­nie ułat­wia wpro­wa­dza­nie zmian i roz­sze­rzeń. Dodanie ko­lej­nych, bar­dziej oszczęd­nych sil­ni­ków obli­cze­nio­wych bę­dzie się te­raz spro­wa­dza­ło do za­pi­sa­nia no­wej kla­sy ba­zu­ją­cej na Solver oraz do­da­niu ko­lej­nej po­zyc­ji do roz­wi­ja­nej li­sty nazw algo­ryt­mów.

Jako ko­lej­ny do­daj­my za­tem „spryt­ny” algo­rytm, któ­ry za­miast ba­dać wszyst­kie ko­lej­ne wie­lo­krot­no­ści bę­dzie spraw­dzał… od ra­zu wy­ni­ki. Jeżeli ilo­raz po­tenc­jal­ne­go wy­ni­ku i licz­by wej­ścio­wej jest licz­bą cał­ko­wi­tą, wy­nik jest po­praw­ny. Ponie­waż po­tenc­jal­nych wy­ni­ków jest du­żo mniej, niż mnoż­ni­ków licz­by wej­ścio­wej, po­win­niś­my uzys­kać du­żą oszczęd­ność licz­by ite­ra­cji, a co za tym idzie — cza­su.

Pozosta­je do roz­wią­za­nia prob­lem: jak ge­ne­ro­wać ko­lej­ne po­praw­ne wy­ni­ki? Można to ro­bić na wie­le spo­so­bów (w tym re­kur­syw­nie), war­to jed­nak za­uwa­żyć, że 10, 11, 100, 101, 110, 111 to tak na­praw­dę ko­lej­ne licz­by bi­nar­ne. Wystar­czy za­tem za­pi­sać pęt­lę li­czą­cą od 2 w gó­rę, prze­kształ­cić in­deks pęt­li na po­stać bi­nar­ną i od­wró­cić prze­kształ­ce­nie, trak­tu­jąc ją jed­nak ja­ko po­stać dzie­sięt­ną:

function SmartSolver() {
   Solver.call(this);
}

SmartSolver.prototype = Object.create(Solver.prototype);

SmartSolver.prototype.solveInternal = function(value) {
   var potentialResult, x;
   for (var i = 2;; ++i) {
      this.numIterations++;
      potentialResult = i.toString(2);
      if (potentialResult.length > this.lengthLimit) return false;
      x = parseInt(potentialResult) / value;
      if (x === parseInt(x)) return x;
   }
};

<select id="method">
 <option value="BruteForceSolver">brute force</option>
 <option value="SmartSolver">smart</option>
</select><br/>

Nowa me­to­da da­je te sa­me wy­ni­ki, jed­nak w du­żo krót­szym cza­sie. Dla pros­tych przy­pad­ków, ta­kich jak licz­ba 5, za­miast dwóch ite­ra­cji wy­nik uzys­ku­je­my po jed­nej. Jednak już licz­ba 3 wy­ma­ga tyl­ko 6 ite­ra­cji za­miast 37, a licz­ba 19 — 24 za­miast 579.

Oczywiś­cie, są też przy­pad­ki od­wrot­ne. Na przy­kład licz­ba 11101, od ra­zu ma­ją­ca właś­ci­wą po­stać, jest roz­pa­try­wa­na przez algo­rytm brute force w cza­sie jed­nej ite­ra­cji, pod­czas gdy „spryt­ny” algo­rytm wca­le nie oka­zu­je się ta­ki spryt­ny i po­trze­bu­je do te­go sa­me­go 28 ite­ra­cji. Nic jed­nak nie stoi na prze­szko­dzie, by wpro­wa­dzić dwa ulep­sze­nia:

Oto im­ple­men­tac­ja no­we­go, spraw­niej­sze­go algo­ryt­mu:

function SmarterSolver() {
   Solver.call(this);
}

SmarterSolver.prototype = Object.create(Solver.prototype);

SmarterSolver.prototype.solveInternal = function(value) {
   if (this.isValidResult(value)) return 1;
   var potentialResult, x;
   var i = parseInt(Math.log2(value));
   for (;; ++i) {
      this.numIterations++;
      potentialResult = i.toString(2);
      if (potentialResult.length > this.lengthLimit) return false;
      x = parseInt(potentialResult) / value;
      if (x === parseInt(x)) return x;
   }
};

<select id="method">
 <option value="BruteForceSolver">brute force</option>
 <option value="SmartSolver">smart</option>
 <option value="SmarterSolver">smarter</option>
</select><br/>

Dla pierw­szych 15 liczb na­tu­ral­nych uzys­ku­je się na­stę­pu­ją­ce wy­ni­ki:

Liczba Liczba ite­ra­cji Wynik
BruteForce Smart Smarter
1 0 0 0 1
2 5 1 2 10
3 37 6 7 111
4 25 3 3 100
5 2 1 1 10
6 185 13 13 1110
7 143 8 8 1001
8 125 7 6 1000
9 12345679 510 509 111111111
10 1 1 0 10
11 1 2 0 11
12 925 27 26 11100
13 77 8 7 1001
14 715 17 16 10010
15 74 13 12 1110

Wnioski są na­stę­pu­ją­ce:

  1. Optyma­li­za­cja punk­tu star­to­we­go opła­ca się do­pie­ro przy więk­szych war­to­ściach wej­ścio­wych. Dla ma­łych liczb nie da­je nic lub wręcz po­gar­sza wy­nik (co da­ło­by się zni­we­lo­wać od­po­wied­nim wa­run­kiem);
  2. Liczba ite­ra­cji rów­na 0 ozna­cza za­dzia­ła­nie wa­run­ku spraw­dza­ją­ce­go, czy po­da­na licz­ba nie jest od ra­zu wy­ni­kiem. Tę opty­ma­li­zac­ję, za­sto­so­wa­ną tyl­ko w ostat­nim przed­sta­wia­nym al­go­ryt­mie, moż­na by za­im­ple­men­to­wać w me­to­dzie solve kla­sy ba­zo­wej, udo­sko­na­la­jąc w ten spo­sób wszyst­kie ist­nie­ją­cej oraz przy­szłe sil­ni­ki obli­cze­nio­we.

Dla cie­ka­wych, kom­plet­na wer­sja stro­ny jest do­stęp­na tu­taj. Ewentu­al­ne do­pra­co­wa­nie ko­du lub na­da­nie pro­gra­mo­wi bar­dziej ele­ganc­kiej po­sta­ci gra­ficz­nej po­zo­sta­wiam Czytel­ni­kom. Szczególnie po­le­cam szu­ka­nie włas­nych me­tod roz­wią­za­nia prob­le­mu, da­ją­cych wy­nik w jesz­cze mniej­szej licz­bie ite­ra­cji.