Príklad z brožúrky o prímačkách na FMFI UK, 2007

p360t · Napísal **p360t**: 17.04.2007 17:43

Toto je príklad štvrtý (nie všetky príklady majú takéto zadanie, väčšinou ide o riešenie konkrétneho problému a to sem dávať je trochu odveci).

Citácia:

Napíšte program, ktorý vypíše všetky slová (postupnosti znakov) dĺžky 6, ktoré sú zložené len z písmen {a, b}. Vypisujte len slová, v ktorých nie je viac písmen b ako písmen a. Program napíšte v ľubovoľnom programovacom jazyku, ktorý ste používali na strednej škole. Takýmito slovami sú napr. abbaba, baabaa, aaaaaa.

Tak, začínam to riešiť, ak máte náladu, skúste aj vy. Ja použijem PHP (už som doma a Pascal, aj keď je na toto vhodnejší, nedisponuje tak komfortným textovým editorom akým je PSPad

). Keď budem hotový, linknem riešenie, porovnáme... Dovtedy sa trápte :breakup:

, možno sem časom pridám ďalšie príklady.

audiotrack · Napísal **audiotrack**: 17.04.2007 18:41

že trápte sa

hneď ma napadli dve riešenia...

p360t · Napísal autor témy **p360t**: 17.04.2007 19:05

audiotrack píše:

že trápte sa

hneď ma napadli dve riešenia...

No veď ich sem šupni (aspoň slovne opíš, ak sa ti nechce písať kód)

Ja mám jedno, ale asi nie je ideálne, žerie dosť systémových prostriedkov.

audiotrack · Napísal **audiotrack**: 17.04.2007 19:10

fúú slovne opísať je niekedy ešte zložitejšie ako napísať kod. No proste rekurziou pre jedno b, backtrackingom pre dve a tri béčka
A teraz ma napadlo úúúplne niečo iné, čo je asi najefektívnejšie, ale to si musím ešte ovoriť či to pôjde

p360t · Napísal autor témy **p360t**: 17.04.2007 19:35

Ok, moje riešenie (mal by som ho aj skôr, ale viete, prišla frajerka, večera, pivo atď

):

Kód:

<?php
    $p['1']="a";
    $p['2']="b";
    // dlzka 6, pismena A a B, nesmie byt viac B ako A    
    // mame viacero moznosti: 3a + 3b, 4a + 2b, 5a + 1b, 6a + 0b
        
    // je tu postupne zanorenych 6 cyklov - aby sme mali istotu, ze sa vystriedaju vsetky
    // kombinacie (bude ich dokopy 64 - aj tych, kde je viac pismen B ako povoluje zadanie)
    for ($l['1'] = 1; $l['1'] <= 2; $l['1']++) {
       for ($l['2'] = 1; $l['2'] <= 2; $l['2']++) {
          for ($l['3'] = 1; $l['3'] <= 2; $l['3']++) {
          for ($l['4'] = 1; $l['4'] <= 2; $l['4']++) {
            for ($l['5'] = 1; $l['5'] <= 2; $l['5']++) {
               for ($l['6'] = 1; $l['6'] <= 2; $l['6']++) {
                // aby sme odfiltrovali slova s B viac ako 3krat, zratame vyskyt Acok a Bcok
                // v slove - aby to bolo jednoduchsie, zvolil som prechadzanie polom $l, v
                // ktorom su ulozene vsetky pismena slova
                $poc = "";
                foreach ($l as $key=>$value) {
                    switch ($p[$l[$key]]) {
                    case "a": $poc['0']++;                     
                       break;
                    case "b": $poc['1']++;
                      break;
                  }
                }
                // tu je uz len jednoducha podmienka, ktora spravi odfiltrovanie podla zadania
                if ($poc['0'] >= $poc['1']) {
                  // zostavime slovo z jednotlivych pismen a ulozime do pola
                   $slova[]=$p[$l['1']].$p[$l['2']].$p[$l['3']].$p[$l['4']].$p[$l['5']].$p[$l['6']];
                }                                
              }
            }
          }
        }
      }
    }
    // vystup - vypiseme obsah pola so slovami
    echo "<pre>\n";
    print_r($slova);
    echo "</pre>";
    ?>

Je možné, že sa to tu nezobrazí pekne, každopádne, tu je link na výsledok:
http://vs.fotopriestor.sk/matfyz-04.php

A ešte niečo - tu je jedno z riešení podľa tej knižky (Pascal, alebo čo to je):

Kód:

const
z: array[0..1] of char = 'ab';
var
i, j, n, k: integer;
s: string;
begin
for i := 0 to 63 do
begin
   s:= '';
   n:= i;
   k:= 0;
   for j := 1 to 6 do 
   begin
      s:= s+z[n mod 2];
      if n mod 2 = 0 then inc(k);
      n:= n div 2;
   end;
   if k >= 3 then
      writeln(s);
   end;
end;

Jaro · Napísal **Jaro**: 17.04.2007 19:43

no trvalo mi to ale na to ze som o php dost dlho nezakopol tak dufam ze aspon trochu dobre :rolleyes:

Kód:

<?php
$ab = create_function('$a','    $i=0;
                                $b=0;
                                $arr1 = str_split($a);
                                for(;$i<=6;$i++)
                                {
                                  if($arr1[$i]==1)
                                  $b++;
                                };
                                return "$b";');

$a=0;
for(;$a<63;$a++)
{
  $c=0;
  $d=decbin($a);
  $c=$ab($d);
  if($c<=3)
  {
    $trans = array(0 => "a", 1 => "b");
    
    if($a<2)
      echo "aaaaa";
     elseif($a<4)
      echo "aaaa";
     elseif($a<8)
      echo "aaa";
     elseif($a<16)
      echo "aa";
     elseif($a<32)
      echo "a";    
    echo strtr($d, $trans);
    echo "<br>";
  };
} 
?>

Príklad z brožúrky o prímačkách na FMFI UK, 2007

Podobné témy