Pages: [1]   Go Down
Print
Author Topic: un esercizio di ricorsione  (Read 1032 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 3.079



WWW
« on: 22-03-2013, 15:03:28 »

Forse e' gia' nella pagina degli esercizi, ma ve lo segnalo
perche' potrebbe risultare ostico per gli imperative-minded

Una funzione (Scheme per ora) che prende una lista e un predicato
e restituisce una lista di due liste, in cui la prima sono gli elementi
che soddisfano il predicato e la seconda gli altri.

Salutoni

FB
Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 3.079



WWW
« Reply #1 on: 25-03-2013, 15:33:27 »

Sono contento che il vostro collega Eilergrab abbia provato a risolvere l'esercizio.
Ho pero' cancellato la sua soluzione affinche' non influenzasse negativamente i lettori.
Funzionava, pero' era una funziona Scheme che, anziche' prendere in input una lista e
un predicato, aveva un argomento in piu'..... e a cosa serviva l'argomento in piu'?....  eh!?!?

Dobbiamo esercitarci con la ricorsione. La soluzione deve avere come argomenti
solo la lista e il predicato. E non deve utilizzare funzioni ausiliarie.

Salutoni
FB
Logged
Acicatena86
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 404


See full me now who neon


« Reply #2 on: 25-03-2013, 15:43:09 »

Sono contento che il vostro collega Eilergrab abbia provato a risolvere l'esercizio.
Ho pero' cancellato la sua soluzione affinche' non influenzasse negativamente i lettori.
Funzionava, pero' era una funziona Scheme che, anziche' prendere in input una lista e
un predicato, aveva un argomento in piu'..... e a cosa serviva l'argomento in piu'?....  eh!?!?

Dobbiamo esercitarci con la ricorsione. La soluzione deve avere come argomenti
solo la lista e il predicato. E non deve utilizzare funzioni ausiliarie.

Salutoni
FB


Pensare imperativo-> ricorsione di coda-> Bocciati fino al 2047  pray

Logged
Eleirgab
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 344


Apprezzatemi ora. Eviterete la fila


WWW
« Reply #3 on: 25-03-2013, 16:14:54 »

anziche' prendere in input una lista e
un predicato, aveva un argomento in piu'..... e a cosa serviva l'argomento in piu'?....  eh!?!?

Serviva a gestire condizioni del tipo "X OperatoreDiConfronto Valore" (pe X > 5), l'argomento in più era proprio il Valore   
Logged

Collettivo SDAI

-----BEGIN GEEK CODE BLOCK-----
Version: 3.1
GIT d-- s+:+ a-- C++ UL++ P L+++ E- W+++>$ N? o? K- w-- O? M V? PS++ PE- Y+ PGP- t 5? X+ R>+ tv-- b++ DI+++ D- G e h! r y+
------END GEEK CODE BLOCK-----
Pandemia000
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 1.714


Γνῶθι Σεαυτόν


« Reply #4 on: 26-03-2013, 11:39:26 »

Code:

(define (restOfBody ls) (cdr (car(cdr (cdr ls)))))
(define (appendList ls x) (append  ls (list x)))
(define (getHead ls)  ( if (null? (car (cdr (cdr ls)))) null
                         (car (car (cdr (cdr ls))))
                       ))
(define (getFirstList ls) ( car ls) )
(define (getSecondList ls) ( car (cdr ls)))

(define (esB ls pred?) (
                         cond [(list? (car ls))
                               (
                                cond [ (null? (getHead ls)) (list (getFirstList ls) (getSecondList ls))]
                                     [(pred? (getHead ls))
                                        (esB (list (appendList (getFirstList ls)(getHead ls)) (getSecondList ls) (restOfBody ls)) pred?)
                                     ]
                                     [else  (esB (list (getFirstList ls) (appendList (getSecondList ls) (getHead ls)) (restOfBody ls)) pred?) ]    
                                )
                              ]
                              [else (esB ( list '() '() ls ) pred?)]
                        
                        )  
 )


Questa è la mia soluzione. Ovviamente le funzioni servono a non impasticciare il codice di parentesi, si possono benissimo includere.
Logged

La disumanità del computer sta nel fatto che, una volta programmato e messo in funzione, si comporta in maniera perfettamente onesta. (Isaac Asimov)
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 3.079



WWW
« Reply #5 on: 26-03-2013, 12:36:35 »

Questa è la mia soluzione. Ovviamente le funzioni servono a non impasticciare il codice di parentesi, si possono benissimo includere.

E guarda caso la ricorsione e' di coda.... 

Credo che con la tua solutione si cerchi di mettere la polvere sotto il tappeto.
Non usi argomenti ausiliari, ma la chiamata ricorsiva la fai su un argomento che ha una
struttura sospettosamente complessa....

FB
Logged
Eleirgab
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 344


Apprezzatemi ora. Eviterete la fila


WWW
« Reply #6 on: 26-03-2013, 18:35:35 »

Secondo tentativo:

Code:
(define (divideList ls pred?)
  (if (null? ls) (list '() '() )
     
      (if(pred? (car ls))
         (list (append (list (car ls)) (car (divideList (cdr ls) pred?))) (car (cdr (divideList (cdr ls) pred?)) ))
         (list (car (divideList (cdr ls) pred?)) (append (list (car ls)) (car (cdr (divideList (cdr ls) pred?)))))
         
      )
  )
)
Logged

Collettivo SDAI

-----BEGIN GEEK CODE BLOCK-----
Version: 3.1
GIT d-- s+:+ a-- C++ UL++ P L+++ E- W+++>$ N? o? K- w-- O? M V? PS++ PE- Y+ PGP- t 5? X+ R>+ tv-- b++ DI+++ D- G e h! r y+
------END GEEK CODE BLOCK-----
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 3.079



WWW
« Reply #7 on: 26-03-2013, 18:43:46 »

Secondo tentativo:

Code:
(define (divideList ls pred?)
  (if (null? ls) (list '() '() )
     
      (if(pred? (car ls))
         (list (append (list (car ls)) (car (divideList (cdr ls) pred?))) (car (cdr (divideList (cdr ls) pred?)) ))
         (list (car (divideList (cdr ls) pred?)) (append (list (car ls)) (car (cdr (divideList (cdr ls) pred?)))))
         
      )
  )
)

Benissimo!

Una piccola osservazione:
al posto di

(append (list (car ls)) (car (divideList (cdr ls) pred?))

io avrei messo

(cons (car ls) (car (divideList (cdr ls) pred?) )


Se a qualcuno la soluzione proposta non risultasse chiara, me lo faccia presente a lezione.

Salutoni
FB

Logged
Pages: [1]   Go Up
Print
Jump to: