indukcja - Matma

Matma / indukcja

Autor	Wiadomość
	Posted: 21 Sty 2001 16:10:07 Mam 1 lutego egzamin z matematyki dyskretnej i nie moge poradzic sobie z nastepujacymi zadaniami: 1. const k=..., type T=array[1..k] of integer; for i - 1 to k-1 do if T[i]<T[i+1] then "zamień T[i] z T[i+1]" writelin (T[k]); Udowodnij , ze powyższy algorytm w pseudopascalu wypisuje maksymalną wartość tablicy T. (Wskazówka : Zastosuj indukcję wzdlędem i. Zastosuj predykat P(i) "po wykonaniu i -tego kroku pętli element maksymalny znajduje się w polu tablicy o indeksie większym niż i") 2. const k=..; type T _array [1..k] of integer ; for i =1 to k-1 do for j+1 to k-i do if T[j] < T[j+1] then "zamień T[j] z T[j+1]" Udowodnij , że powyższy algorytm w pseudopascalu sortuje tablicę T. (Wskazówka : Zastosuj indukcję względem i . Skorzystaj z zadania poprzedniego. Określ wyraźnie predykat P, który występuje w Twoim dowodzie (zapewne inny niżw poprzednim zadaniu )). 3. W mieści Skrzyżne nie ma ślepych ulic (tzn. jadąc dowolnąulicąw dowolnym kierunku zawsze dojedziemy do skrzyżowania ) i wszystkie ulice sądwukierunkowe . Do każdego skrzyżowania dochodiz parzysta liczba ulic . Z każdego skrzyżowania można dojechać do każdego innego skrzyżowania . Udowodnij, że można w tym mieście przejechać tylko jeden raz , rozpoczynając i kończąc podróż na tym samym skrzyżowaniu . (Wskazówka :zastosuj indukcję względem liczby ulic. Skorzystaj z silniejszej wersji zasady indukcji matematycznej (krok indukcyjny: jezeli [P(s) ^ P(s+1)^..^P(n)] to p(n+1) 4.Pokaż ,że dla dowolnej liczby naturalnej n istnieje liczba naturalna c taka , ze jeżeli połączymy odcinkami każde dwa wierzchołki K-kąta foremnego , gdzie k=c , to przy dowolym pokolorowaniu wszystkich tych odcinków n kolorami pewne trzy odcinki będące bokami jednego trójkąta uzyskaja ten sam kolor. 5. Które z poniższych implikacji logicznych sa prawdziwe . Dla każdej nieprawdziwej implikacji przedstaw kontrprzykład dokładnie definiując predykat P. [P(1) i (dla kazdego n nalezacego do narutalnych){P(n^2) implikuje p((n+1)^2} i (dla każdego n nalezacego do narutalnych){P(n+1) implikuje (P(n))}] to implikuje ((dla kazdego n nalezacego do narutalnych){P(n)) [P(125) i (dla kazdego n nalezacego do narutalnych){P(n^2) implikuje p((n^2 + 2n + 2)} i (dla każdego n nalezacego do narutalnych){P(n+1) implikuje (P(n))}] to implikuje ((dla kazdego n nalezacego do narutalnych){P(n)) 6. Udowodnij , że poniższy program wypisuje wyłącznie liczby całkowite . x:=1; while (1<2)do begin writeln (x); x:= x+sqrt(12(x-1)+3; end ; prosze o pilny kontakt jestem w wielkiej potrzebie za odpowiedzi serdecznie dziekuje
wak	Posted: 21 Sty 2001 18:51:42 Mam 1 lutego egzamin z matematyki dyskretnej i nie moge poradzic sobie z nastepujacymi zadaniami: 6. Udowodnij , że poniższy program wypisuje wyłącznie liczby całkowite . x:=1; while (1<2)do begin writeln (x); x:= x+sqrt(12(x-1)+3; end ; ile to jest 1+sqrt(12(1-1))+3 lub 1+sqrt(12(1-1)+3) nie wiem gdzie "konczy sie pierwiastek"


° Forum ° Odpowiedz ° Rejestracja ° Szukaj °