RSS

Klub Mistrzów Komputera trzydzieści lat później: ciągi operacji

Liczba odsłon: 102

„Klub Mistrzów Komputera” to dział publi­ko­wa­ny trzy­dzie­ści lat te­mu na ła­mach cza­so­pis­ma Komputer. Do Klubu mog­ły na­le­żeć oso­by, któ­rym uda­ło się roz­wią­zać publi­ko­wa­ne za­da­nia oraz na­de­słać włas­ne pro­po­zyc­je za­ga­dek dla in­nych klu­bo­wi­czów oraz kan­dy­da­tów.

Niektóre z publi­ko­wa­nych za­dań są trud­ne na­wet w dzi­siej­szych realiach. Inne ukie­run­ko­wa­ne są na kon­kret­ne kom­pu­te­ry lub ję­zy­ki pro­gra­mo­wa­nia i z dzi­siej­sze­go punk­tu wi­dze­nia nie są zbyt cie­ka­we. Wiele jed­nak sta­no­wi in­te­re­su­ją­ce ła­mi­głów­ki zwią­za­ne z ana­li­zą i prze­twa­rza­niem da­nych. Jedno z ta­kich za­dań, opu­bli­ko­wa­ne w nu­me­rze 7/1987, chciał­bym tu­taj przy­pom­nieć i roz­wią­zać.

Oto treść za­da­nia:

Mając do dys­po­zyc­ji czte­ry trój­ki, zna­ki pod­sta­wo­wych dzia­łań moż­na na­pi­sać wy­ra­że­nia, któ­rych war­tość jest rów­na 1, 2, 3 itd., np.

3-3 + 3/3 = 1,
3/3 + 3/3 = 2, ...

Proponu­ję na­pi­sać uni­wer­sal­ny pro­gram na two­rze­nie ta­kich wy­ra­żeń (tzn. da­ne dla pro­gra­mu to licz­ba na­tu­ral­na i licz­ba jej wy­stą­pień, a wyj­ście po­win­no za­wie­rać wy­ra­że­nia o wszyst­kich moż­li­wych do uzys­ka­nia war­to­ściach).

Przy za­ło­że­niu nie­wiel­kie­go roz­mia­ru roz­wią­zy­wa­ne­go prob­le­mu, za­da­nie moż­na roz­wią­zać na­wet ręcz­nie, trak­tu­jąc je ja­ko ćwi­cze­nie umys­łu. Dużo cie­kaw­sze jest jed­nak na­pi­sa­nie pro­gra­mu sa­mo­czyn­nie wy­szu­ku­ją­ce­go właś­ci­we cią­gi ope­rac­ji. Ponadto, ta­ki pro­gram da­je nam moż­li­wość eks­pe­ry­men­to­wa­nia z da­ny­mi wej­ścio­wy­mi i szu­ka­nia ta­kich pa­ra­met­rów, dla któ­rych uzys­ku­je się jak naj­wię­cej po­praw­nych roz­wią­zań.

Próbując za­pi­sać kil­ka liczb wed­ług przed­sta­wio­nych w treś­ci za­da­nia re­guł mo­że­my spo­strzec sche­ma­ty, zgod­nie z któ­ry­mi moż­na zbu­do­wać kon­kret­ne war­toś­ci. Na przy­kład, dla do­wol­nej war­toś­ci x wy­ra­że­nie x/x zaw­sze da wy­nik 1, a wy­ra­że­nie x-x da wy­nik 0. Ambitni mo­gą wy­ko­rzys­tać tę wie­dzę, by spró­bo­wać stwo­rzyć pro­gram bu­du­ją­cy cią­gi ope­rac­ji w spo­sób al­go­ryt­micz­ny. Dopóki jed­nak nie bę­dzie­my pró­bo­wać roz­pa­try­wać zbyt du­żej iloś­ci da­nych, po­dejś­cie brute force jest jak naj­bar­dziej real­ne, a przy tym du­żo prost­sze do zrea­li­zo­wa­nia.

Jedyną opty­ma­li­zac­ją, któ­rą fak­tycz­nie moż­na za­sto­so­wać nie­wiel­kim na­kła­dem środ­ków, jest ogra­ni­cze­nie za­kre­su funkcjo­no­wa­nia pro­gra­mu. Przy za­ło­że­niu, że je­dy­ny­mi do­pusz­czal­ny­mi ope­ra­cja­mi są do­da­wa­nie, odej­mo­wa­nie, mno­że­nie i dzie­le­nie, naj­więk­sza moż­li­wa do za­pi­sa­nia licz­ba to xy, gdzie x to czyn­nik cią­gu, a y to je­go dłu­gość.

Najpoważ­niej­szym prob­le­mem, z ja­kim zet­knie się oso­ba pi­szą­ca pro­gram, jest wy­zna­cza­nie war­toś­ci go­to­we­go, zbu­do­wa­ne­go wy­ra­że­nia, ta­kie­go jak 3-3 + 3/3. Robiąc to, na­le­ży wziąć pod uwa­gę ko­lej­ność po­szcze­gól­nych ro­dza­jów dzia­łań. Na szczęś­cie, nie­któ­re ję­zy­ki pro­gra­mo­wa­nia roz­wią­zu­ją ten prob­lem za nas, udo­stęp­nia­jąc funk­cje ana­li­zu­ją­ce wy­ra­że­nia aryt­me­tycz­ne. Na przy­kład, w ję­zy­ku Java­Script dzia­ła­nie ta­kie reali­zu­je funk­cja eval():

eval('3+3-3/3')
5

Java­Script ma jesz­cze jed­ną, wiel­ką za­le­tę: go­to­wy pro­gram mo­że­my za­pi­sać w for­mie apli­kac­ji sie­cio­wej, do­stęp­nej dla użyt­kow­ni­ków do­wol­ne­go kom­pu­te­ra i sys­te­mu opera­cyj­ne­go, na któ­rym dzia­ła no­wo­czes­na prze­glą­dar­ka inter­ne­to­wa. W ten spo­sób za­da­nie sprzed trzy­dzie­stu lat roz­wią­zu­je­my w spo­sób, któ­ry wte­dy był ma­rze­niem, a dziś jest czymś co­dzien­nym i oczy­wis­tym.


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="element">Czynnik:</label>
  <input id="element"/><br/>
  <label for="length">Liczba czynników:</label>
  <input id="length"/><br/>
  <label for="min">Od liczby:</label>
  <input id="min"/><br/>
  <label for="max">Do liczby:</label>
  <input id="max"/><br/>
  <button type="button" onclick="perform();">Wyznacz</button>
 </fieldset>
</form>
<pre id="result"></pre>

Wczyta­my za je­go po­mo­cą czte­ry 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.

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: 9em;
}
input {
 margin: 2pt;
}

Pierwszym kro­kiem na dro­dze do roz­wią­za­nia prob­le­mu po­win­na być je­go de­kom­po­zy­cja obiek­to­wa. Najważniej­szym obiek­tem, z ja­kim ma­my tu­taj do czy­nie­nia, jest sam ciąg ope­rac­ji. Ciąg jest opi­sa­ny na­stę­pu­ją­cy­mi in­for­mac­ja­mi:

Obiekt cią­gu mu­si ofe­ro­wać na­stę­pu­ją­ce ope­rac­je (me­to­dy):

Ponadto kla­sa obiek­tu cią­gu ope­rac­ji po­win­na mieć za­pi­sa­ną wspól­ną, nie­zmien­ną ba­zę sym­bo­li czte­rech dzia­łań pod­sta­wo­wych, któ­re są do­pusz­czal­ne w ra­mach cią­gu.

Zacznijmy od stwo­rze­nia i zde­fi­nio­wa­nia kon­struk­to­ra obiek­tu. Klasę na­zwie­my ElementChain:

function ElementChain(element, length) {
   this.element = element;
   this.absMax = Math.pow(element, length);
   this.ops = [];
   for (var opIdx = 0; opIdx < length - 1; ++opIdx)
      this.ops.push(this.privates.allOps[0]);
}

ElementChain.prototype.privates = {
   'allOps': [ '+', '-', '*', '/' ]
};

Konstruk­tor, po­za za­ini­cja­li­zo­wa­niem obiek­tu kla­sy, wy­li­cza war­tość absMax za­wie­ra­ją­cą mo­duł mak­sy­mal­nej war­toś­ci, ja­ką moż­na uzys­kać za po­mo­cą cią­gu o za­da­nej dłu­goś­ci, ba­zu­ją­ce­go na czyn­ni­ku o po­da­nej war­toś­ci. Daje to w przy­szło­ści moż­li­wość zmniej­sze­nia na­kła­du pra­cy.

Przetesto­wa­nie dzia­ła­nia kon­struk­to­ra jest moż­li­we z po­zio­mu kon­so­li pro­gra­mi­stycz­nej prze­glą­dar­ki WWW:

var obj1 = new ElementChain(3, 4);
var obj2 = new ElementChain(9, 9);
obj1
Object { element: 3, numOps: 3, absMax: 81, ops: Array[3] }
obj2
Object { element: 9, numOps: 8, absMax: 387420489, ops: Array[8] }

Kolejną ope­ra­cją, któ­rą war­to za­im­ple­men­to­wać, jest prze­kształ­ca­nie obiek­tu na po­stać tek­sto­wą, na­da­ją­cą się do wy­świet­la­nia na ekra­nie. Standar­do­wym spo­so­bem uzys­ka­nia ta­kie­go re­zul­ta­tu jest nad­pi­sa­nie stan­dar­do­wej me­to­dy toString():

ElementChain.prototype.toString = function() {
   var s = '';
   for (var i = 0; i < this.ops.length; ++i)
      s = s + this.element + this.ops[i];
   s += this.element;
   return s;
};
var obj1 = new ElementChain(3, 4);
var obj2 = new ElementChain(9, 9);
obj1.toString();
"3+3+3+3"
obj2.toString();
"9+9+9+9+9+9+9+9+9"

Gdy dy­spo­nu­je­my już spo­so­bem na prze­kształ­ce­nie obiek­tu cią­gu w za­pis sen­sow­ny z punk­tu al­ge­bry, mo­że­my wy­ko­rzys­tać moż­li­woś­ci ję­zy­ka Java­Script, by wy­zna­czyć nu­me­rycz­ną war­tość tak za­pi­sa­ne­go cią­gu:

ElementChain.prototype.getValue = function() {
   return eval(this.toString());
};

Zostało nam tyl­ko użyć me­to­dy brute force, by zna­leźć ta­ką kom­bi­nac­ję sym­bo­li ope­rac­ji, któ­ra po­zwo­li uzys­kać właś­ci­wy wy­nik. Można te­go do­ko­nać al­bo ite­ra­cyj­nie, al­bo re­kur­syw­nie. Rozwiąza­nia ite­ra­cyj­ne są za­zwy­czaj szyb­sze i oszczęd­niej­sze, jed­nak roz­wią­za­nie re­kur­syw­ne cha­rak­te­ry­zu­je się więk­szą czy­tel­no­ścią i zwar­to­ścią, co ma po­zy­tyw­ny efekt dy­dak­tycz­ny. Oto za­tem pro­po­zyc­ja wy­ko­rzy­stu­ją­ca re­ku­ren­cję:

ElementChain.prototype.aimFor = function(value) {
   if (value < -this.absMax || value > this.absMax) return false;
   return this.privates.aimFor.call(this, value, 0);
};

ElementChain.prototype.privates.aimFor = function(value, position) {
   for (var opIdx = 0; opIdx < this.privates.allOps.length; ++opIdx) {
      this.ops[position] = this.privates.allOps[opIdx];
      if (position === this.ops.length - 1) {
         if (this.getValue() === value) return true;
      } else {
         if (this.privates.aimFor.call(this, value, position + 1)) return true;
      }
   }
   return false;
};

Metoda aimFor() do­stęp­na bez­po­śred­nio w obiek­cie słu­ży tyl­ko za fa­sa­dę: spraw­dza, czy uzys­ka­nie wy­ni­ku jest w ogó­le moż­li­we oraz wy­wo­łu­je ukry­tą wer­sję re­kur­syw­ną z ze­rem ja­ko nu­me­rem mo­dy­fi­ko­wa­ne­go sym­bo­lu ope­rac­ji. Dopiero ukry­ta wer­sja me­to­dy dla każ­de­go moż­li­we­go sym­bo­lu umiesz­cza­ne­go na wska­za­nej po­zyc­ji ana­li­zu­je wy­nik, mo­dy­fi­ku­jąc w ra­zie po­trze­by rów­nież dal­sze ope­ra­to­ry.

Na ko­niec zo­sta­je funk­cja po­bie­ra­ją­ca da­ne z for­mu­la­rza i uru­cha­mia­ją­ca obli­cze­nia:

function perform() {
   var element = parseInt(document.getElementById('element').value);
   var length = parseInt(document.getElementById('length').value);
   var min = parseInt(document.getElementById('min').value);
   var max = parseInt(document.getElementById('max').value);
   var result = '';
   var timeStart = performance.now();
   var elementChain = new ElementChain(element, length);
   for (var value = min; value <= max; ++value) {
      var successful = elementChain.aimFor(value);
      result += value + ': ' + (successful ? elementChain : '-') + "\r\n";
   }
   var timeEnd = performance.now();
   result += "\r\nCzas obliczeń: " + (timeEnd - timeStart) + ' ms';
   document.getElementById('result').innerHTML = result;
}

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 jed­nak po­le­cam za­sta­no­wie­nie się nad roz­wią­za­niem te­go sa­me­go prob­le­mu w spo­sób al­go­ryt­micz­ny, z wy­ko­rzys­ta­niem wspom­nia­nych złą­czeń par czyn­ni­ków. Warto też za­sta­no­wić się nad wy­łą­cze­niem funkcjo­nal­noś­ci wy­szu­ki­wa­nia właś­ci­we­go roz­wią­za­nia do od­dziel­nej kla­sy tak, aby roz­dzie­lić za­kres od­po­wie­dzial­noś­ci po­szcze­gól­nych obiek­tów i umoż­li­wić im­ple­men­to­wa­nie róż­nych algo­ryt­mów wy­zna­cza­nia roz­wią­za­nia.