Řešili jsme následující úlohu:

Bezpečnost zámku je mimo jiné dána počtem klíčů které lze k danému typu zámku vyrobit. Pokud by jich bylo málo stačí si opatřit všechny možné klíče a u každého zámku je vyzkoušet. Pokud je takových klíčů moc, je tento způsob pro zloděje neatraktivní (nebojte se mají lepší metody). Uvažujme následující klíč:

Ten má obecně NZ zubů (v našem případě 7), z nichž každý může dosahovat NU úrovní (na obrázku 4). Úroveň sousedních zubů se může lišit maximálně o MR (na obrázku je to 1), jinak by nebylo možno klíč vyrobit tak, aby jej šlo hladce zasunout do zámku. Navrhněte algoritmus a napište program, který pro zadané NZ, NU a NR určí počet klíčů, které je možno vyrobit. Prověřte si svoje klíče od domu! Ten na obrázku lze vyrobit 1220-ti způsoby.

V tomto souboru je program se dvěma procedurami. Jedna řeší úlohu rekurentním algoritmem prohledávajícím všechny možnosti s časovou složitostí řádu (2NR+1)^nz , druhá používá chytřejší algoritmus se složitostí řádu NZ*NU*NR. Jeho optimalizací lze získat algoritmus(není předveden) složitosti řádu NZ*NU.

Domácí úkol: Úloha DU1: Batoh a valouny zlata