Scheme

Na página da disciplina de FP no IST Alameda:
No projecto só podem usar os tipos do Scheme que já foram dados nas aulas teóricas e aparecem no livro (não podem usar vectores). Tem que ser usado o tipo lista dado nas aulas teóricas.
Clicar para expandir...

De qualquer forma, o objectivo do projecto é fazer-nos puxar pela cabeça. Com vectores seria tudo demasiado fácil ;)

Se é ou não preciso usarmos vectores na segunda parte do projecto, só amanhã, quando recebermos o enunciado, é que saberemos :D
 
Kayvlim disse:
Na página da disciplina de FP no IST Alameda:


De qualquer forma, o objectivo do projecto é fazer-nos puxar pela cabeça. Com vectores seria tudo demasiado fácil ;)

Se é ou não preciso usarmos vectores na segunda parte do projecto, só amanhã, quando recebermos o enunciado, é que saberemos :D
Clicar para expandir...

Não é mais fácil...é diferente. Ao invés de andares a fazer juggling com a lista de função para função, tens que fazer sets.
 
tenho uma dúvida...
eu comecei a semana passada a dar tabelas, e numa das implementações de tabela, recorria a hashing.

podem dar exemplos em scheme de uma função hash????
 
Boas,

Tenho de fazer um programa que dando uma lista com numeros e um numero (2 argumentos) ela devolva uma lista (com alguns dos elementos da lista dada) que somados dêem esse numero, ou se não houver nenhuns numeros, a função devolve a lista vazia.

O meu problema é saber como é que vou calcular todas as somas, porque a lista tem um numero variavel de elementos.

Não quero que me façam o trabalho (não é essa a ideia), e quero ser eu a fazer um código, mas precisava de uma ajuda com o problema das somas...não há nenhum algoritmo para fazer isto??


Cumps
 
Infelizmente esse problema é NP-Completo aka vais ter de resolver por brute force.

Uma forma simples de resolver recursivamente (mas não muito simpática em termos de memória) é gerares a potência dessa lista de inteiros e depois calcular a soma para cada lista da potência até encontrares uma que dê.
 
IComeFromBehind disse:
Infelizmente esse problema é NP-Completo aka vais ter de resolver por brute force.

Uma forma simples de resolver recursivamente (mas não muito simpática em termos de memória) é gerares a potência dessa lista de inteiros e depois calcular a soma para cada lista da potência até encontrares uma que dê.
Clicar para expandir...

Não percebi bem a tua ideia, mas se calhar acho que também não me expliquei muito bem. Vou dar um exemplo:

(procedimento '(2 3 4 5) 9) -> (4 5)
(procedimento '(2 3 4 5) 30) -> ()

Quanto á memória não te preocupes...primeiro há que por o programa a funcionar e depois é que se corrige essas falhas :D


De qualquer forma obrigado pela resposta.


EDIT: O que eu tenho que fazer é ver todas as somas com 2 elementos, 3 elementos, ... até encontrar alguma que dê o resultado, ou então devolver a lista vazia.
 
Desculpa, mas mesmo assim não percebi nada...não percebo o quê que isso das potências tem a ver com o meu problema!!

O que eu tenho de fazer é dada uma lista e um numero, a função tem de returnar uma lista em que os seus elementos somados dão o numero que eu inseri ou se n houver combinações de numeros que deêm retorna a lista vazia.

Basicamente tenho de fazer todas as somas com 2 elementos da lista, depois com 3, depois com 4,... até encontrar um conjunto de parcelas que dêem a soma, ou se não houver, devolve a lista vazia. O meu problema é não saber como fazer isso uma vez que a lista tem um numero variavel de elementos.


Cumps
 
Tem tudo a haver com o teu problema. Imagina que a tua lista é um conjunto, na verdade não é mas não interessa. Se gerares uma lista com todas as sub-listas da tua lista e depois percorreres recursivamente essa lista de lista verificado de cada vez se a soma dos seus elementos dá aquilo que pretendes. Se der retornas essa lista se nao continuas.

EDIT: bah fica aqui um exemplo tá em OCaml porque eu nao sei scheme mas o esquema deve ser mais ou menos o mesmo. (Nao garanto que compile).
Código: 
let rec sums_to list number = match list with
	[] -> number = 0
	| x::xs -> sums_to xs (number - x)
;;

let rec has_sum_to list_of_lists number = match list_of_lists with
	[] -> []
	| x::xs -> if sums_to x number then x else has_sum_to xs number
;;

let rec power l = 
    match l with 
          [] -> [[]] 
        | x::xs -> let powered_list = power xs in powered_list @ List.map (fun y -> x::y) (powered_list) 
;;

let rec add_to list number = 
	let powered_list = power list in
	has_sum_to powered_list number
;;
 
Última edição:
Finalmente consegui perceber a tua ideia, que era mesmo o que eu pretendo. O problema agora é fazer um programa para isso :D

Até agora já fiz isto, mas não está bem, porque não me dá todas as combinações e a lista que devia ter todas as combinações está muito confusa. Se me podesses dar uma ajuda com o código agradecia.


Código: 
(define pertence?
  (lambda (e c)
    (if (null? c)
        #f
        (or (equal? e (car c))
            (pertence? e (cdr c))))))
(define uniao
  (lambda (a b)
    (cond
      ((null? a) b)
      ((not (pertence? a b)) (cons a b)))))
(define f
  (lambda (e t)
    (uniao e t)))
(define conjunto-potencia
  (lambda (s)
    (if (null? s)
        s
        (let* ((e (car s))
               (t (cdr s)))
          (uniao (conjunto-potencia t) (f e (conjunto-potencia t)))))))


Por exemplo: (conjunto-potencia '(1 2 3)) -> (((3) 2 3) 1 (3) 2 3) ->isto é uma autêntica confusão :x
 
IComeFromBehind disse:
Código: 
let rec sums_to list number = match list with
    [] -> number = 0
    | x::xs -> sums_to xs (number - x)
;;
 
let rec has_sum_to list_of_lists number = match list_of_lists with
    [] -> []
    | x::xs -> if sums_to x number then x else has_sum_to xs number
;;
 
let rec power l = 
    match l with 
          [] -> [[]] 
        | x::xs -> let powered_list = power xs in powered_list @ List.map (fun y -> x::y) (powered_list) 
;;
 
let rec add_to list number = 
    let powered_list = power list in
    has_sum_to powered_list number
;;
Clicar para expandir...

Giro.

Ronnie_03 disse:
Código: 
(define pertence?
  (lambda (e c)
    (if (null? c)
        #f
        (or (equal? e (car c))
            (pertence? e (cdr c))))))
(define uniao
  (lambda (a b)
    (cond
      ((null? a) b)
      ((not (pertence? a b)) (cons a b)))))
(define f
  (lambda (e t)
    (uniao e t)))
(define conjunto-potencia
  (lambda (s)
    (if (null? s)
        s
        (let* ((e (car s))
               (t (cdr s)))
          (uniao (conjunto-potencia t) (f e (conjunto-potencia t)))))))
Por exemplo: (conjunto-potencia '(1 2 3)) -> (((3) 2 3) 1 (3) 2 3) ->isto é uma autêntica confusão :x
Clicar para expandir...

Sim, uma autêntica confusão. O procedimento f não faz sentido. Não precisas de utilizar um let*. O teu caso terminal não está correcto, uma vez que deveria ser (()) e não (). A união que precisas de fazer não é bem a que implementaste. Calcular duas vezes o mesmo conjunto-potencia não é definitivamente uma boa ideia :007:.

Segue uma possível solução:

Código: 
> (define (conjunto-potencia s)
       (if (null? s)
           '(())
           (let ((t (conjunto-potencia (cdr s)))
                  (e (car s)))
             (append t (map (lambda (c) (append (list e) c)) t)))))
 
> (conjunto-potencia '(1 2 3))
(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))
 
 
; Em seguida, basta filtrares os elementos deste conjunto cuja soma não seja igual ao número. Algo do género:
 
(define (conjunto-soma s number)
  (filter (lambda (subset) (= (apply + subset) number))
          (conjunto-potencia s)))
 
> (conjunto-soma '(1 19 2 18 3 17 4 16) 20)
((1 3 16) (1 2 17) (1 19) (2 18) (3 17) (4 16))

Podes também utilizar o outro método que está descrito na wikipedia, e que utiliza os números binários, embora não fique muito interessante quando implementado em Scheme. Em Python, seria algo do género:

Código: 
def powerset(s):
    sets = []
    indicator = lambda x: x & 1
    for element in xrange(2**len(s)):
        n = element
        subset = []
        for x in s:
            if indicator(n):
                subset.append(x)
            n >>= 1
        sets.append(subset)
    return sets
 
> powerset([18,19,20])
[[], [18], [19], [18, 19], [20], [18, 20], [19, 20], [18, 19, 20]]

Qualquer dúvida, coloca aqui.
 
AliFromCairo disse:
Giro.
Código: 
> (define (conjunto-potencia s)
       (if (null? s)
           '(())
           (let ((t (conjunto-potencia (cdr s)))
                  (e (car s)))
             (append t (map (lambda (c) (append (list e) c)) t)))))
 
> (conjunto-potencia '(1 2 3))
(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))
 
 
; Em seguida, basta filtrares os elementos deste conjunto cuja soma não seja igual ao número. Algo do género:
 
(define (conjunto-soma s number)
  (filter (lambda (subset) (= (apply + subset) number))
          (conjunto-potencia s)))
 
> (conjunto-soma '(1 19 2 18 3 17 4 16) 20)
((1 3 16) (1 2 17) (1 19) (2 18) (3 17) (4 16))

Qualquer dúvida, coloca aqui.
Clicar para expandir...

Muito obrigado pela ajuda...só utilizei a primeira função, porque o meu problema era apenas gerar o conjunto potencia (o resto eu sabia fazer), depois passei esse conjunto e o numero que eu queria a outra função e ela para cada elemento da lista fazia a soma dos elementos que estavam nesse elemento da lista e se fosse igual ao numero pedido o programa devolvia esse elemento e parava...se não encontrase nenhuma combinação devolvia a lista vazia.

Apesar de não ter usado a tua segunda função, percebi bem o que querias dizer, era só obter os elementos que me interessassem e depois devolver um qualquer.


EDIT: Não percebi muito bem como é que funciona a ultima linha da função conjunto potência.


Cumps
 
Última edição:
A ideia da última linha é concretizar o que está na wikipedia, e que diz que P(S) = P(T) U F(e, P(T)). P(T) é o conjunto potência de T = S\{e} que se encontra na variável t (powerset (cdr s)) do let. O {e} também se encontra na variável e do let (car s). A função F o que faz é juntar (append) o elemento {e} a cada um dos elementos de P(T). Para tal, utilizei a função map que aplica uma função a cada um dos elementos da lista. Neste caso, a função é (lambda (c) (append (list e) c)), que faz precisamente aquilo que escrevi acima, ou seja, junta o {e} a cada um dos elementos de P(T). Optei por uma função anónima, mas podias perfeitamente implementar essa função e dar-lhe um nome.

Exemplificando, considera que tens o conjunto S = {1, 2, 3}. Neste caso, {e} vai ser igual a {1}, e T vai ser igual a S\{1} = {2, 3}, ou seja, P(T) = { {} {2} {3} {2 3} }. Através deste P(T) percebes que o que vais ter de fazer é juntar (append) o P(T) à lista que contém todos os elementos de P(T) U {1}. Ou seja, o teu conjunto final vai ser P(S) = { {} {2} {3} {2 3} } U { {1} {1 3} {1 2} {1 2 3} }.

Isto é capaz de ter ficado relativamente confuso, mas acho que deu para perceber a ideia.

Qualquer dúvida, avisa.
 
boas...

numa dos trabalho que tinha que fazer era criar uma abstracção de dados Anel...

Aqui está a minha versão
Código:

Código: 
#lang scheme

(require r5rs/init)

;; anel

;; © 2008 [EMAIL="[email protected]"][email protected][/EMAIL]

;; Abstracção 'Anel'

;; Representação e implementação da Abstracção 'Anel' via
;; listas com recurso a mutação 


;; Definições
 (define nil '())
 
 
 
;; Contructor
 
;; cria-anel:  -> Anel<X>
;; devolve um anel vazio
 (define (cria-anel)
   (cons 'anel nil))
 

;; Selector

;; corrente: Anel<X> -> X | indefinido
;; retorna o valor corrente de um anel,
;; dá erro se o anel estiver vazio
 (define (corrente anel)
   (if (anel-vazio? anel)
       (error "corrente de anel vazio" anel)
       (cadr anel)))
 
 
 
 
;; Operations

;; anel?: qualquertipo -> booleano
;; retorna verdadeiro caso o objecto seja um anel e falso
;; caso contrário
(define (anel? anel)
  (and (pair? anel)
       (eq? 'anel (car anel))))

;; anel-vazio?: Anel<X> -> booleano | indefinido
;; retorna verdadeiro caso o anel esteja vazio, falso
;; caso o anel não esteja vazio ou erro caso o objecto não
;; seja um anel
(define (anel-vazio? anel)
  (if (not (anel? anel))
      (error "o objecto não é um anel: " anel)
      (null? (cdr anel))))

;; seguinte: Anel<X> -> indefinido
;; faz com que o elemento a seguir ao elemento corrente passe a ser
;; o elemento corrente
 


;; Mutators


;; insere!: Anel<X>, X -> indefinido

 (define (insere! anel elem)
   (cond ((not (anel? anel)) (error "o objecto não é um anel:" anel))
         (else (set-cdr! anel (cons elem (cdr anel))))))
 
;; remove!: Anel<X> -> indefinido
 
 (define (remove! anel)
   (cond ((not (anel? anel)) (error "o objecto não é um anel:" anel))
         ((anel-vazio? anel) (error "o anel encontra-se vazio:" anel))
         (else (set-cdr! anel (cddr anel)))))
mas uma das operações é fazer com que o anel rode, à semelhança das pistolas antigas, se é que me estou a fazer entender

aqui está a minha tentativa para esse procedimento
Código:
Código: 
(define (seguinte anel)
   (cond ((not (anel? anel)) (error "o objecto não é um anel:" anel))
         ((anel-vazio? anel) (error "o anel encontra-se vazio:" anel))
         (else (cons (cddr anel) (cadr anel)))))


como é que consigo dar rotatividade à lista?


Podem-me ajudar??????
 
Última edição:
Boas,

Precisa da vossa ajuda para um procedimento, sff

Eu queria fazer um procedimento que retira-se o primeiro elemento da lista( que seria o procedimento de nome retira), e que pega-se nesse elemento e verifica-se se existe um car + 1 ou um car -1 desse elemento na lista( que seria o procedimento de nome verifica)

por exemplo

> (define m ( list ( cons 2 3) ( cons 3 3) ( cons 2 8)))
> (retira 1 m)
(2.3)
> (verifica 1 m)
#t

Ou seja seriam dois procedimento..um que retirava o elemento e outro que verificava se existe um car + 1 ou um car -1 desse elemento na lista
 
Inicie sessão ou registe-se para poder participar.
Back
Topo