"Torben Ægidius Mogensen" <torbenm@diku.dk> wrote in message
news:w5zntzoc5w.fsf@pc-032.diku.dk...
> "Katrine" <hatikvah83@hotmail.com> writes:
<SNIP>
>> hele opgaven kan ses her:
> >
http://www.imada.sdu.dk/Courses/DM13/oblopg/obl1.pdf ).
> >
> > Mit problem er hovedsageligt tilgangen til spørgsmål 1 og 2 - jeg ved
> > simpelthen ikke hvad jeg skal gøre og gribe i. Hvordan vises det, at
> > menterne kan udtrykkes rekursivt som ci og hvordan skal jeg gribe
> > induktionsbeviset an?
> >
> > Håber en gut eller to kan komme med et godt input :)
>
> Søg på "carry-lookahead adder" på nettet (eller i din lærebog).
>
Det er muligt jeg ikke fik udtrykt mig klart nok: Jeg kan sagtens forstå,
hvad det er, der rent faktisk sker. Jeg kan godt forstå, at det sker i
logaritmisk tid og at det er smart. Hvad jeg ikke kan er:
1) "Vise" at menterne for i > 0 kan udtrykkes rekursivt som c[i] =
a[i-1]b[i-1] + (a[i-1] XOR b[i-1])c[i-1]
2) Induktionsbevise at c[i] = G[i-1] for i=1,2,...,n-1.
> Torben
Mvh
Katrine