Przeglądałem sobie stare wydania Komputera i znalazłem tam takie
zadanie:

#v+
8/1990 W książce .Opowieści matematyczne. dr Michał Szurek podaje jak
wyrazić 1983 za pomocą jedynek:

1983 = (1+1+1)*{1+(1+1+1)*(1+1+1+1)*(1+1+1+1+1)*[(1+1+1)*(1
+1+1)+1+1]}

Proponuję napisać program podający dla danej liczby
minimalną liczbę jedynek pozwalającą wyrazić tę
liczbę (dopuszczalnymi operacjami są tylko dodawanie
i mnożenie; nie wolno łączyć jedynek w liczby
wielocyfrowe).
#v-

Zastanawiam się od której strony zacząć (ewentualnie o co pytać google),
bo podejście naiwne wydaje się "trochę" czasochłonne ;->

PS: Nie, nie jest to żadne zadanie na uczelnię :-) Pochodzi z
miesięcznika Komputer, z numeru 7-12/90, z działu Klub Mistrzów
Komputera.
--
/\-\/\-\/\-\/\-\/\-\/\-\/\ My name is drzewo, /dev/drzewo
\ K...@e...eu.org /
/ http://epsilon.eu.org/ \
\/-/\/-/\/-/\/-/\/-/\/-/\/

do góry

'Twas brillig when Mariusz Kruk wrote:
> Przeglądałem sobie stare wydania Komputera i znalazłem tam takie
> zadanie:
> #v+
> 8/1990 W książce .Opowieści matematyczne. dr Michał Szurek podaje jak
> wyrazić 1983 za pomocą jedynek:
> 1983 = (1+1+1)*{1+(1+1+1)*(1+1+1+1)*(1+1+1+1+1)*[(1+1+1)*(1
+1+1)+1+1]}
> Proponuję napisać program podający dla danej liczby
> minimalną liczbę jedynek pozwalającą wyrazić tę
> liczbę (dopuszczalnymi operacjami są tylko dodawanie
> i mnożenie; nie wolno łączyć jedynek w liczby
> wielocyfrowe).
> #v-
> Zastanawiam się od której strony zacząć (ewentualnie o co pytać google),
> bo podejście naiwne wydaje się "trochę" czasochłonne ;->
> PS: Nie, nie jest to żadne zadanie na uczelnię :-) Pochodzi z
> miesięcznika Komputer, z numeru 7-12/90, z działu Klub Mistrzów
> Komputera.

Tak na logikę:

-Rozłożyć liczbę na czynniki pierwsze
- Jeśli dany czynnik N >5 rozłożyć na czynniki [N-1] i dodać jedynkę
(np. n=7 do postaci 1+2*3)
- Powtarzać dopóki żadna z liczb nie jest większa od 5
- Zsumować wszystkie liczby.

Pytanie tylko czy jest to rozwiązanie optymalne? :)

Pozdrawiam,
Kiełpiś

--
Pieczło, jaszczągów maźnych rój Tomasz Kiełpiński
Wiroświdrował na zegawie, a.k.a. "Kiełpiś"
Błahudy był szczoptaków strój Odpowiadając prywatnie,
I gwiczał świbłąk w trawie usuń: FALSZYWY z adresu

do góry

On Thu, 22 Jan 2009 22:42:17 +0100, Mariusz Kruk wrote:

> #v+
> 8/1990 W książce .Opowieści matematyczne. dr Michał Szurek podaje jak
> wyrazić 1983 za pomocą jedynek:
>
> 1983 = (1+1+1)*{1+(1+1+1)*(1+1+1+1)*(1+1+1+1+1)*[(1+1+1)*(1
+1+1)+1+1]}
>
> Proponuję napisać program podający dla danej liczby
> minimalną liczbę jedynek pozwalającą wyrazić tę
> liczbę (dopuszczalnymi operacjami są tylko dodawanie
> i mnożenie; nie wolno łączyć jedynek w liczby
> wielocyfrowe).
> #v-

http://www.waset.org/pwaset/v31/v31-119.pdf

--
Marcin Balcerzak

do góry

Marcin Balcerzak pisze:
>
> http://www.waset.org/pwaset/v31/v31-119.pdf
>

Wydawało mi się, że w (1) wystarczy min(1+f(n-1),f(d)+f(n/d)),
co daje złożoność O(n^1.5). Czy ktoś udowodnił,
że 1+f(n-1) <= f(e)+f(n-e) dla 1<=e<=n/2? W każdym razie
"empirycznie" się zgadza.

P.

do góry

On Wed, 28 Jan 2009 19:31:06 +0100, Piotrne wrote:

> Marcin Balcerzak pisze:
>>
>> http://www.waset.org/pwaset/v31/v31-119.pdf
>>
>
> Wydawało mi się, że w (1) wystarczy min(1+f(n-1),f(d)+f(n/d)),
> co daje złożoność O(n^1.5). Czy ktoś udowodnił,
> że 1+f(n-1) <= f(e)+f(n-e) dla 1<=e<=n/2? W każdym razie
> "empirycznie" się zgadza.
>
> P.

Nie sprawdzales dla 21080618 prawda?:)
Poszukaj sobie o hipotezach Davida Wilsona. Problem nie jest taki prosty,
jak Ci sie wydawalo.

--
Marcin Balcerzak

do góry