Ðàçáîð çàäà÷

Ñì. ../../03_DataTypes

• Ïåðåäàòü input() ÷òî-íèáóäü äåéñòâèòåëüíî íåõîðîøåå:

  • Ôóíêöèÿ __import__() îòêðûâàåò ïðîñòîð ñàìûì îìåðçèòåëüíûì ÷óäåñàì:

    >>> input()

    __import__("os").system("cd /; ls")

    bin   dev  home  lib64       media  opt   root  sbin     srv  tmp  var
    boot  etc  lib   lost+found  mnt    proc  run   selinux  sys  usr
    0
    >>>

• ../../03_DataTypes/Homework_RepeatedString

  • Ïðèìåð ?ðåøåíèÿ íà Ïàñêàëå? áåç ïðèìåíåíèÿ ìîçãà:

       1 s=raw_input()
       2 repeat=0
       3 for i in xrange(1,len(s)+1):
       4     found=1
       5     for k in xrange(1,len(s)/i):
       6         equal=0
       7         for j in xrange(i):
       8             if s[j]==s[j+i*k]:
       9                 equal+=1
      10         if equal==i:
      11             found+=1
      12     if found*i==len(s):
      13         if repeat<found:
      14             repeat=found
      15 print repeat
    

    • Çäåñü âñå ïëîõî, êðîìå òîãî, ÷òî ðåøåíèå ðàáîòàåò:

    • Off-by-One â öèêëàõ/ñðàâíåíèÿõ (ïî÷åìó â ñòðîêàõ 2-6 òî 1, òî 0?)

    • Ðàáîòà ñî ñòðîêàìè êàê ñ ìàññèâàìè (ñòðîêîâûå ìåòîäû íà ÷òî?)
    • ãëóïîâàòûé àëãîðèòì (ñì. äàëåå)
  • Ïðèìåð ðåøåíèÿ íà Python (ìîçã íå âêëþ÷àåì):

       1 s = raw_input()
       2 repeat = 1
       3 for i in xrange(1,len(s)+1):
       4     newrep = s.count(s[:i])
       5     if newrep*i == len(s):
       6         if newrep > repeat:
       7             repeat = newrep
       8 print repeat
    

    • Ïàðó ñëîâ ïðî àëãîðèòì:

    • Çà÷åì ñíà÷àëà ñ÷èòàòü âõîæäåíèÿ ïîäñòðîêè â ñòðîêó, à çàòåì âûÿñíÿòü, ÷òî íè÷åãî è íå ìîãëî ïîëó÷èòüñÿ, ïîòîìó ÷òî äëèíà ñòðîêè íå êðàòíà äëèíå ïîäñòðîêè?

    • Ìàêñèìóì óáûâàþùåé ïîñëåäîâàòåëüíîñòè ìîæíî áûëî áû èñêàòü è ïîýôôåêòèâíåå

  • Êîðîòêîå ðåøåíèå:

       1 s = raw_input()
       2 for i in xrange(1, len(s)+1):
       3     if not len(s)%i and s.count(s[:i])*i == len(s):
       4             print len(s)/i
       5             break
    

    • Ðåøåíèå íå îïòèìàëüíî (âìåñòî xrange íàäî áû âçÿòü ñïèñîê äåëèòåëåé, à count ïðîõîäèò ïî âñåé ñòðîêå, õîòÿ íàñ óñòðîèë áû ïåðâûé æå ñáîé ïîèñêà)

    • Ðåøåíèå çàíèìàåò âñåãî 5 ñòðîê. Ýòî íîðìàëüíî
  • Ðåøåíèå ñ èçáûòî÷íûì ïðèìåíåíèåì ìîçãà:

       1 print (lambda s: (len(s)/i for i in xrange(1, len(s)+1) if not len(s)%i and s.count(s[:i])*i == len(s)).next())(raw_input())
    

    • Ëþáóþ çàäà÷ó ìîæíî ðåøèòü â îäíó ñòðîêó ôóíêöèîíàëüíûì ïóòåì. Íî íå âñåãäà íóæíî.