Inne, zadanie nr 530
ostatnie wiadomo艣ci | regulamin | latex
| Autor | Zadanie / Rozwi膮zanie |
aaakuuus02 post贸w: 19 |  2012-10-09 16:11:22Obliczy膰, ile r贸偶nych podzbior贸w mo偶na utworzy膰 ze zbioru n-elementowego :) z g贸ry dzi臋kuje i prosz臋 o wyja艣nienie, dlaczego w艂a艣nie tak,a nie inaczej, pozdrawiam ;)) |
tumor post贸w: 8070 | 2012-10-09 16:45:28 Elementy w zbiorze n-elementowym mo偶emy ponumerowa膰. Ka偶dy element mo偶e by膰 w podzbiorze (to oznaczmy $1$), albo te偶 mo偶e go nie by膰 (to oznaczmy $0$). W贸wczas np dla 3-elementowego zbioru $\{a,b,c\}$ podzbiory opisa膰 mo偶na tak: $000$ - podzbi贸r pusty $001$ $010 = \{b\}$ $100$ $011 = \{b,c\}$ $101$ $110$ $111$ - ca艂y zbi贸r Prawda? A ile jest ci膮g贸w o d艂ugo艣ci $n$, kt贸rych wyrazy s膮 $0$ lub $1$? Oczywi艣cie $2^n$. To w艂a艣nie liczba podzbior贸w zbioru n-elementowego. ---------- To samo osi膮gamy indukcyjnie. Zbi贸r 1-elementowy ma dwa podzbiory, czyli $2^1$. Je艣li za艣 zbi贸r n-1-elementowy ma $2^{n-1}$ podzbior贸w i dodamy do zbioru jeden nowy element, to liczba podzbior贸w podwoi si臋 (bo do ka偶dego podzbioru mo偶emy ten nowy element doda膰 otrzymuj膮c nowy podzbi贸r lub nie dodawa膰, dwa wyj艣cia). Czyli dla n-elementowego dostajemy $2^n$. |
aaakuuus02 post贸w: 19 | 2012-10-09 17:01:19 oo, dzi臋kuje bardzo za odpowied藕 :) ! |
| strony: 1 | |
Prawo do pisania przys艂uguje tylko zalogowanym u偶ytkownikom. Zaloguj si臋 lub zarejestruj