logowanie

matematyka » forum » forum zadaniowe - uczelnie wyższe » zadanie

Inne, zadanie nr 985

ostatnie wiadomości  |  regulamin  |  latex

AutorZadanie / 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





© 2019 Mariusz Śliwiński      o serwisie | kontakt   drukuj