Tags:
create new tag
view all tags

Scomposizione di un numero

Supponiamo di avere una sequenza v0, v1, ..., vN di N+1 numeri interi, che chiameremo operandi, e un numerro intero T, che chiameremo il totale.

Diremo che il totale Ŕ ottenibile dagli operandi quando ((...(wN opN wN-1)...) op2 w1) op1 w0 = T dove w0, w1, ..., wN Ŕ una permutazione degli operandi e ogni operatore opi indica una delle quattro operazioni aritmetiche di base (somma, sottrazione, prodotto e divisione intera), con il vincolo che la divisione puo' eseguita solo se il dividendo Ŕ multiplo del divisore; ovvero, 15/5 puo' essere eseguita, mentre 12/5 no). Ad esempio, data la sequenza 3, 10, -2, il totale 24 puo' essere ottenuto con (-2 + 10) * 3 = 24. Si osservi che, data una sequenza di operandi, in generale la sequenza di operazioni che permette di ottenere il totale non Ŕ unica (banalmente, 2+2=4 e 2*2=4).

  1. Scrivere una funzione ricorsiva C di prototipo
    int contaScomposizioni1(int N, int v[], int T)
    che riceve in input il numero N di operazioni da eseguire per ottenere il totale T a partire dagli N+1 operandi contenuti nel vettore v[] e restituisce il numero di modi in cui pu˛ essere ottenuto il totale assumendo per˛ che non sia possibile cambiare l'ordine degli operandi. In pratica, si devono contare le sequenze di N operzioni tali che ((...(vN opN vN-1)...) op2 v1) op1 v0 = T
  2. Scrivere una funzione ricorsiva C di prototipo
    int contaScomposizioni2(int N, int v[], int T)
    analoga a quella del punto 1, considerando per˛ tutte le possibili permutazioni degli operandi.
  3. Scrivere una funzione ricorsiva C di prototipo
    int contaScomposizioni3(int N, int v[], int T, int sum, int sub, int mult, int div)
    simile alla fuzione del punto 1 ma che conta solo i modi in cui si pu˛ ottenere il totale usando sum addizioni, sub sottrazioni, mult moltiplicazioni e div divisioni (ovviamente, N=sum+sub+mult+div). Come per la funzione del punto 1, l'ordine degli operandi non pu˛ essere cambiato.
  4. Scrivere una funzione ricorsiva C di prototipo
    int contaScomposizioni3(int N, int v[], int T, int sum, int sub, int mult, int div)
    simile alla fuzione del punto 3, considerando per˛ tutte le possibili permutazioni degli operandi.

-- StefanoGuerrini - 03 May 2007

Edit | Attach | Watch | Print version | History: r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r2 - 2007-05-04 - StefanoGuerrini






 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
Torna al Dipartimento di Informatica
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2021 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback