Inne, zadanie nr 985
ostatnie wiadomości | regulamin | latex
Autor | Zadanie / Rozwiązanie |
sidleniwiec666 postów: 8 | 2013-01-30 11:31:10 Numerując stronice książki, napisano 630 cyfr. Ile stron miała książka> zapisz algorytm pozwalający szybko rozwiązać podobne zadania. |
dudzina15 postów: 1 | 2013-05-14 23:43:14 Może ktoś podać algorytm jak wykonać to zadanie? |
zorro postów: 106 | 2013-05-23 07:06:33 Dane: x=ilość użytych cyfr Szukane: s=liczba stron Zmienna pomocnicza (index): k=0,1,2,3,4,... Start: Niech $x_{0}=x$ $k=0$ Krok 1: $k=k+1$ $x_{k}=x_{k-1}-9k*10^{k-1}$ Warunek: Jeżeli $x_{k}> 0$ to przejdź do kroku 1, w przeciwnym razie przejdź do kroku 2. Krok 2: Szukana liczba stron: $s=(10^{k-1}-1)+\frac{x_{k-1}}{k}$ Stop. Sprawdzamy jak algorytm działa dla 630 cyfr. $x_{0}=630$ $k=0$ Krok 1 $k=0+1=1$ $x_{1}=x_{0}-9*1*1=630-9=621$ $x_{1}=621>0$ więc powtarzamy krok 1: $k=1+1=2$ $x{2}=621-9*2*10=621-180=441$ $441>0$ więc znów powtarzamy krok 1: $k=2+1=3$ $x_{3}=441-9*3*100=441-2700 <0$ więc wykonujemy krok 2 $s=(10^{2}-1)+\frac{x_{2}}{3}=99+\frac{441}{3}=99+147=246$ Odp: Książka liczy 246 stron. Wiadomość była modyfikowana 2013-05-25 08:30:02 przez zorro |
zorro postów: 106 | 2013-05-23 07:23:10 Dla wyjaśnienia jak to zrobiłem: 1. Stron jednocyfrowych może być co najwyżej 9. Jeśli cyfr jest więcej niż 9 to książka musi mieć także strony dwucyfrowe. 2. Każda strona dwucyfrowa wymaga "zużycia" dwóch cyfr na swój nr. Stron dwucyfrowych może być co najwyżej 99-9=90, co wymaga 2*90=180 cyfr do zapisu. Jeśli jest więcej niż 9+2*90 cyfr to muszą być też strony trzycyfrowe 3. Każda strona trzycyfrowa oznaczana jest trzema cyframi. Maksymalnie może być 999-99=900 stron trzycyfrowych na które potrzeba 3*900 cyfr. Jeśli liczba cyfr przekracza 1*9+2*90+3*900 to dochodzimy do stron czterocyfrowych 4. Itd. 5. Jeśli stron n-cyfrowych jest mniej niż $9*10^{n-1}$ to całkowita liczba cyfr pomniejszona o ilość cyfr potrzebnych do zapisu stron 1-cyfrowych, 2-cyfrowych ... i (n-1)cyfrowych, będzie się dzielić bez reszty przez n. Taka jest idea, reszta to główkowanie. |
strony: 1 |
Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj