Probleme in Scheme

; verificare daca o lista e palindroma

(define (palindrome? lista)

(let secv ((l1 lista) (l2 (reverse lista)))

(cond

((null? l1)

#t) ; s-a ajuns la sfarsitul listelor fara probleme => palindrom

((= (car l1) (car l2)) ; daca sunt egale se apeleaza secventa pt restul listelor

(secv (cdr l1) (cdr l2)))

(#t ; nu s-a apelat secventa din nou => inegalitate si lista nu e palindroma

#f)))

)

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; toate elementele dintr-o lista de liste etc, adunate intr-o sg lista

(define flatten

(lambda (lista)

(cond ((null? lista) '())

((pair? (car lista)) ; daca car este o lista

(append (flatten (car lista)) ; apeleaza fct flatten pt car si pt cdr , si apoi le impreuneaza

(flatten (cdr lista))))

(else ; daca car este un sg element

(cons (car lista) ; il insereaza

(flatten (cdr lista))))))) ; la lista rezultata in urma aplicarii flatten asupra restului de lista curenta

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; multimea tuturor submultimilor ale unei multimi

(define (power-set lista)

(if (null? lista) '(())

(let ((rest (power-set (cdr lista)))) ; salveaza fct aplicata pe restul de lista

(append rest ; pe care il adauga

(map (lambda (sublista) ; la ceea ce rezulta prin aplicarea cons inceputului de lista dintr-o sublista si acelui rest

(cons (car lista) sublista))

rest))

)))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; produsul cartezian a 2 liste

(define make ; produs cartezian de un singur element cu o lista

(lambda(x lista)

(if (null? lista) '()

(cons (append (list x) (list(car lista))) (make x (cdr lista)) )

)))

(define cart-2

(lambda(list1 list2)

(if (or (null? list2)(null? list1)) '()

(append (make(car list1) list2) ; aplica fct make pentru fiecare prim elem din prima lista, cu lista a doua

(cart-2 (cdr list1) list2)) ; se aplica acelasi procedeu pt ceea ce ramane din prima lista cu lista a doua

)))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; produsul cartezian a n liste

(define (cart-22 l1 l2) ; var mai buna de a calcula cart-2

(foldl

(lambda (x res)

(append

(foldl

(lambda (y acc) (cons (cons x y) acc))

'() l2) res))

'() l1))

(define (cp lofl) ; cart-n insa cu puncte

( if(null? lofl) '()

( foldl cart-22 (first lofl) (rest lofl))))

(define conv-dot ; converteste o lista cu puncte intr-una fara

(lambda (lista)

( if (null? lista) '()

( if (pair? lista)

(append (list(car lista)) (conv-dot (cdr lista) ) ) (cons lista '())

))))

(define cart-n

(lambda (lista)

(map conv-dot (cp lista))) ; aplica fct de conversie pt toate listele rezultate cu pct

)

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; calcularea nr e

(define inv_fact ; calculeaza 1/nr!

(lambda (nr)

(let loop ((n nr) (index 1))

(if (= n 1)

(if (= index 1)

index

(- index 1))

(loop (/ n index) (+ index 1))))))

(define succ ; succesorul lui n

(lambda (n)

(* n (/ 1 (+ (inv_fact (/ 1 n)) 1)))))

(define make_prog

(lambda (k)

(cons k (lambda ()

(make_prog (succ k))))))

(define prog_stream

(make_prog 1)) ; 1/1! + ....

(define take

(lambda (nr stream)

(let loop((n nr) (st stream) (aux 1))

(if (= n 0)

aux

(loop (- n 1) ((cdr st)) (+ aux (car st)))))))

; verificare:

;(log (take 30 prog_stream))

Problema reginelor

Pe o tablă NxN trebuie așezate N regine astfel încât să nu existe conflicte între oricare 2 piese (o regină poate elimina altă regină dacă segmentul determinat de cele două piese este paralel cu oricare din axele sau diagonalele tablei de joc).

In program, *s este vectorul care retine pe ce linie se afla fiecare regina pusa pe o singura coloana. Ex. s[1]=3 inseamna `regina de pe coloana 1 se afla pe linia 3`.

#include "stdio.h"
#include "stdlib.h"
#include "math.h"

int n , *s;
int vf;

void avans () {

vf++;
s[vf]=-1;

}

int succesor () {

s[vf]++;
return s[vf] < n;

}

int valid () {

int ok = 1;
int i;
for (i=0; i < vf; i++)
if(s[i]==s[vf] || abs(s[vf]-s[i])==vf-i)
ok=0;
return ok;
}

int sol () {

return vf==n-1;
}

void tipar () {

int i,j;
printf("solutie\n");
for(i=0; i < n; i++) {
for(j=0; j < n; j++) {
if(s[i]==j) printf("Q");
else printf("#"); }
printf("\n"); }
printf("\n");
}

void back() {

vf = -1;
avans ();
while(vf > -1) {
if(succesor()) {
if(valid()) { if(sol()) tipar();
else avans(); }
else ; }
else vf--; }
}

int main() {

printf("\n");
printf("n= ");
scanf("%d", &n);
s = (int *) malloc (n*sizeof(int));
back();
return 0;

}

Functii cu continuari in Scheme

Diverse feluri de a calcula suma elementelor unei liste

; in mod normal

(define sum_list

(lambda (l)

(letrec ((sum (lambda (l s)

(if (null? l) s

(sum (cdr l) (+ s (car l)))))))

(sum l 0))))

; cu afisare pe parcurs- propagare de la un apel la altul

(define sum_list

(lambda (l)

(letrec ((sum (lambda (l s)

(if (null? l) s

(let ((result (sum (cdr l) (+ s (car l)))))

(display result)

result))))) ; ultima expresie din secventa dicteaza valoarea la care se evalueaza let, respectiv ramura else

(sum l 0))))

(sum_list '(0 3 6))

; propagare direct catre primul apel

(define sum_list

(lambda (l)

(call/cc ; call continuation

(lambda (cont)

(letrec ((sum (lambda (l s)

(if (null? l) (cont s) ; se abandoneaza , se intoarce in call/cc si il pune pe s

; reia procesul de evaluare a apelului initial, furnizandu-i valoarea corespunzatoare

(let ((result (sum (cdr l) (+ s (car l)))))

(display result)

result)))))

(sum l 0))))))

; (sum_list '(1 2 3)) ; 6

; cu verificare ca ceea ce se aduna e numar

(define sum_list

(lambda (l)

(call/cc

(lambda (cont)

(letrec ((sum (lambda (l s)

(cond

((null? l) (cont s))

((number? (car l)) (sum (cdr l) (+ s (car l))))

(else (cont 0)))))) ; valoarea speciala 0, in caz de eroare - "aruncare de exceptii"

(sum l 0))))))

(sum_list '(1 2 3)) ; 6

(sum_list '(1 2 scheme rulz)) ; 0

; adunarea unor nr cu succ, pred, zero??

; fctii add , sub , mult , div (2 numere) folosind fct si continuari

(define succ

(lambda (x)

(+ x 1)))

(define pred

(lambda (x)

(- x 1)))

(define zero??

(lambda (x)

(if (= 0 x) #t #f)))

(define unu??

(lambda (x)

(if (= 1 x) #t #f)))

; adunare normala

(define add

(lambda (a b)

(cond

((zero?? b) a)

(else (add (succ a) (pred b))))))

; adunare cu continuari

(define add2

(lambda (a b)

(call/cc

(lambda (cont)

(letrec ((adds (lambda (a b)

(if (zero?? b) (cont a)

(let ((result (adds (succ a) (pred b) )))

(display result)

result)))))

(adds a b))))) )

; scadere normala

(define sub

(lambda(a b)

(cond

((zero?? b) a)

(else (sub (pred a) (pred b)))

)))

; scadere cu continuari

(define sub2

(lambda (a b)

(call/cc

(lambda (cont)

(letrec ((subs (lambda (a b)

(if (zero?? b) (cont a)

(let ((result (subs (pred a) (pred b))))

(display result)

result)))))

(subs a b))))))

; inmultire nr naturale

(define mult ; c contor =de la 1 ..... b se aduna a, acum = acumulator

(lambda (a b c acum)

(call/cc

(lambda (cont)

(letrec ((mul (lambda (a b c acum)

(if (= c b) (cont acum)

(let ((acum (add2 acum a)) (c (succ c)))

(mul a b c acum))))))

(mul a b c acum)

)))))

;(mult 3 8 0 0)

; impartire exacta pt nr naturale

(define div

(lambda (a b c) ; c = contor

(call/cc

(lambda (cont)

(letrec ((di (lambda (a b c)

(if (zero?? a) (cont c)

( let ((result (sub2 a b)))

(di result b (succ c)))))))

(di a b 0)

)))))

;(div 21 3 0)

Protocoale cu fereastra glisanta pentru legatura de date

In cazul acestor protocoale, la orice moment de timp, emitatorul mentine o multime de numere de secventa care corespund cadrelor pe care are permisiunea sa le trimita. Aceste cadre apartin unei ferestre de transmisie. Receptorul va mentine o fereastra de receptie (avand de asemenea o multime de numere de secventa) corespunzatoare cadrelor ce pot fi acceptate. Cele doua ferestre (ale emitatorului si receptorului) nu trebuie sa aiba aceeasi dimensiune.

Protocolul cu fereastra glisanta de un bit utilizeaza metoda stop-and-wait, deoarece emitatorul transmite un cadru si asteapta confirmarea sa inaintea transmiterii urmatorului cadru.

Urmatoarea aplicatie emitator / receptor functioneaza conform cu descrierea protocolului cu fereastra glisanta de un bit. Cele doua aplicatii transmit date intre ele prin intermediul unor pipe-uri, contorizand numarul pachetului trimis/receptionat.
Emitatorul trimite cadre dintr-un pachet pe care le contorizeaza, trimite si contorul acestora. Receptorul stie la ce contor sa se astepte, si daca primeste un cadru nedorit, trimite la randul sau propriul contor neupdatat, astfel emitatorul mai trimite o data cadrul respectiv.
In plus, s-a folosit codificarea si decodificarea crc pentru a verifica si mai bine datele. Emitatorul calculeaza propriul tabel crc si, pentru fiecare cadru trimis, calculeaza acumulatorul, pe care il transmite. Receptorul la randul lui si-a creat tabelul crc, primeste acumulatorul dar si calculeaza un nou acumulator pe baza cadrului primit. In plus fata de conditia de concordanta a numarului cadrelor, diferenta intre acumulatoare trebuie sa fie 0.

sender.c

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "unistd.h"
#include "fcntl.h"
#include "sys/types.h"
#include "sys/stat.h"
#include "crc.h"

char *text = "smoke this in your pipe and stuff it please";


int main () {


int fd1, fd2;
fd1 = open ("pipe1", O_RDONLY );
fd2 = open ("pipe2", O_WRONLY );
int inc = 0, i=0, primit=0, j, acum=0;
word *tabel;
tabel = tabelcrc(CRCCCITT);
int ok=1;

do {
if(ok)
crctabel(text[i], &acum, tabel);
ok = 0;
write (fd2, &text[i], 1);
write (fd2, &inc, 4);
write(fd2, &acum, 2);
printf("%d\n",acum);
read (fd1, &primit, 4);
if(primit==inc)
{ inc++;
i++;
ok = 1;
}
} while(i < strlen(text)+1);

close (fd1);
close(fd2);
return 0;

}


receiver.c

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "unistd.h"
#include "sys/types.h"
#include "sys/stat.h"
#include "fcntl.h"
#include "crc.h"


int main () {

int fd1, fd2;
char buf;
int contor=-1;
int cadru;
fd1 = open ("pipe1", O_WRONLY );
fd2 = open ("pipe2", O_RDONLY );
word acum, acum_nou=0;
word * tabel = tabelcrc(CRCCCITT);
word ac;


while(1) {
read ( fd2, &buf, 1);
read ( fd2, &cadru,4);
read(fd2, &acum, 2);

crctabel(buf, &acum_nou, tabel);
ac = acum_nou;
crctabel(ac>>8, &acum, tabel);
crctabel(ac& 0x00FF, &acum, tabel);
// printf("%d\n", acum);
printf ( "%c\n", buf );
if(cadru == contor+1 && acum==0) {
contor++;
write(fd1, &contor, 4);
}
else
write (fd1, &contor, 4);
}

close (fd1);
close (fd2);
return 0;

}

La compilare se va folosi si fisierul crc.c definit aici.

LISP

Click pe poza pt marit!