Po drátě 3: Řešení úlohy č. 12

Zadání je pro změnu program. Je krásně jednoduchý a evidentně nic ošklivého nedělá (za mírně děsivou by se dala považovat snad jenom záhadná řetězcová konstanta pojmenovaná rahc ... pamětníci si jistě vzpomínají). Tak si ho zkusíme zkompilovat a spustit.

Po chvilce vypíše "Gratulujeme! Vyresili js" ... a další písmenka vypisuje pomaleji a pomaleji. Zřejmě na konci textu vypíše heslo, ale sotva to stihne do konce soutěže (nebo aspoň do konce světa).

Pojďme se mu tedy podívat na zoubky zblízka: Vnější cyklus proběhne tolikrát, kolik písmenek má zmíněná konstanta, a za každý svůj krok jedno písmenko vypíše. Jenže další dva cykly do něj vnořené mezitím ještě mnohokrát posunou pozici ve stringu, takže vůbec není jasné, které písmenko se kdy vypíše.

Nejvnořenější ze tří cyklů podezřele připomíná přičítání jedničky k i-cifernému dvojkovému číslu zapsanému po číslicích. Prostřední cyklus opakuje tuto operaci tak dlouho, než přičtení skončí s přenosem z i-tého řádu, tedy po 2ⁱ krocích. Vnější cyklus proto vypíše (2ⁱ mod N)-té písmenko, kde N je délka celého řetězce.

Program tedy stačí přepsat tak, aby rovnou počítal mocniny dvojky modulo N:

#include <stdio.h>
#include <string.h>

int main(void)
{
  const char rahc[] = "Gr atnmt!eVaietus e vyekj j!ai lsiuPvrodayorosloieeaseu znlp h u ei hlrrpisljheacmopcg e bel iinelts:";
  int n, p, q, i;
  p = 0;
  q = 1;
  n = strlen(rahc);
  for (i=1; i<n; i++)
    {
      putchar(rahc[p]);
      p = (p+q) % n;
      q = (q+q) % n;
    }
  putchar('\n');
  return 0;
}

Komentář

Špatnými řešeními vás tentokráte nepobavíme: Všichni, kdo se k této úloze dostali, ji až na triviální chyby (jako vypsání prvního písmenka stringu ještě jednou na konci) vyřešili hned správně.

Úlohu napsal Martin a zase si na tom jednou trošku procvičil základy algebry: délku řetězce je totiž potřeba zvolit tak, abychom mocninami dvojky proskákali všechny znaky, jinými slovy aby dvojka byla generátorem multiplikativní grupy modulo délka řetězce.