Dotaz: Rozklad na sucet

[fishbone1]

vie mi niekto pomoct s tymto programom?... zvolim si cislo n napr n=4 a program ma spravit vsetky mozne rozklady tohto cisla na sucet. teda napr:

1+1+1+1 
1+1+2 
1+3 
2+1+1 
3+1 

nemoze byt pouzita rekurzia....pomoze mi niekto???

---

---

Odpovědi

[12345]

Máme za tebe dělat domácí úkoly?

[fishbone1]

nie ale poradit ako na to.

[wamba]

dobře tak radím

000:1+1+1+1
001:1+1+2
010:1+2+1
011:1+3
100:2+1+1
101:2+2
110:3+1
111:4

(0 napiš mezi čísla +,1 sečti čísla)

[Mips]

Možná jen nesmí být použita triviální rekurze ve smyslu prostého rekurzivního volání funkce pro výpočet rozkladu. Pak se nabízí možnost využít znalost toho, jak taková rekurze funguje, a udělat to sice pořád v principu rekurzivně, ale bez rekurzivního volání té funkce.

[rm -rf *]

http://ksp.mff.cuni.cz/tasks/21/tasks3.html#task5

[Michal Kubeček]

Neurčil jste jazyk, tak jsem si ho zvolil sám. :-)

\newcount\n
\newcount\m
\newcount\i

\def\rozloz#1#2#3{%
  \n=#1
  \m=#2
  \ifnum\m<\n\else#3\the\n\par\fi
  \i=\n
  \advance\i by -1
  \ifnum\i>\m \i=\m\fi
  \ifnum\i>0
    \loop
      \bgroup
        \advance\n by -\i
        \edef\pfx{#3\the\i+}
        \rozloz{\n}{\i}{\pfx}
      \egroup
      \advance\i by -1
    \ifnum\i>0\repeat
  \fi
}

\def\rozklad#1{\rozloz{#1}{#1}{}}

\rozklad{20}

\bye

[Radovan]

To je fakt, měl by napsat v čem to potřebuje naprogramovat :)

 10 DIM pole(1000)
 20 INPUT "Zadej cislo z intervalu <1;1000> ",pole(0)
 30 pole(0)=INT pole(0)
 40 IF pole(0)<1 OR pole(0)>1000 THEN GOTO 240
 50 pozice=1
 60 FOR i=1 TO pole(0)
 70   pole(pozice)=i:soucet=0
 80   FOR j=1 TO pozice
 90     soucet=soucet+pole(j)
100   NEXT j
110   IF soucet<pole(0) THEN GOTO 190
120   PRINT STR$(pole(1));
130   FOR j=2 TO pozice
140     PRINT "+";STR$(pole(j));
150   NEXT j
160   PRINT
170   pozice=pozice-1
180   GOTO 210
190   pozice=pozice+1
200   GOTO 60
210   i=pole(pozice)
220 NEXT i
230 EXIT
240 REM cislo mimo interval
250 PRINT "Sorry vole, ERROR!";CHR$(7)
260 EXIT

A asi by neškodilo upozornit že počet kombinací je 2^(n-1), takže pro n větší než pár desítek by se výsledku nemusel dožít

[Michal Kubeček]

Já bych jich měl méně, protože jsem volil variantu bez permutací (za zadání to není moc jasné, tazatel tam má něco mezi a navíc mu chybí triviální samotná čtyřka). Ale i tak to pro 50 dává pěkných 3647 stran A4 (ve skutečnosti ještě víc, protože je tam spousta přetečených \hboxů).