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

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).

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

Mariusz Kruk pisze:

> 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).

Zobacz:
http://mathworld.wolfram.com/IntegerComplexity.html

P.

do góry

epsilon$ while read LINE; do echo \>"$LINE"; done < "Piotrne"
>> 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).
>
>Zobacz:
>http://mathworld.wolfram.com/IntegerComplexity.html

Na pierwszy rzut oka wygląda zachęcająco. Dzięki.

--
\.\.\.\.\.\.\.\.\.\.\.\.\.\ Prayers are always answered. The answer is
.\....@e...eu.org.\.\. usually no.
\.http://epsilon.eu.org/\.\
.\.\.\.\.\.\.\.\.\.\.\.\.\.

do góry

Mariusz Kruk wrote:
> Przeglądałem sobie stare wydania Komputera i znalazłem tam takie
> zadanie:
>
> 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).
>
> Zastanawiam się od której strony zacząć (ewentualnie o co pytać google),
> bo podejście naiwne wydaje się "trochę" czasochłonne ;->

Wydaje mi się, że analogiczne zadanie to najkrótszy program w
Brainfucku generujący stałą (przy założeniu "non-wrapping"):
http://esoteric.voxelperfect.net/wiki/Brainfuck_cons
tants
Dokładna równoważność będzie chyba, jeśli zamiast "długość programu"
postawimy "liczbą operacji +".

--
Paweł Kierski
n...@p...net

do góry

epsilon$ while read LINE; do echo \>"$LINE"; done < "Paweł Kierski"
> Wydaje mi się, że analogiczne zadanie to najkrótszy program w
>Brainfucku generujący stałą (przy założeniu "non-wrapping"):
>http://esoteric.voxelperfect.net/wiki/Brainfuck_con
stants
>Dokładna równoważność będzie chyba, jeśli zamiast "długość programu"
>postawimy "liczbą operacji +".

No, trochę nie. Brainf*ck nie ma mnożenia. Poza tym, ma odejmowanie.

--
[------------------------] I am Macintosh of Borg, Compatibility is Fu-
[ K...@e...eu.org ] tile!
[ http://epsilon.eu.org/ ]
[------------------------]

do góry

epsilon$ while read LINE; do echo \>"$LINE"; done < "Mariusz Kruk"
>> Wydaje mi się, że analogiczne zadanie to najkrótszy program w
>>Brainfucku generujący stałą (przy założeniu "non-wrapping"):
>>http://esoteric.voxelperfect.net/wiki/Brainfuck_co
nstants
>>Dokładna równoważność będzie chyba, jeśli zamiast "długość programu"
>>postawimy "liczbą operacji +".
>No, trochę nie. Brainf*ck nie ma mnożenia. Poza tym, ma odejmowanie.

Wróć. Nie zauważyłem wrapping/non-wrapping. Ale uwaga o mnożeniu
zostaje.

--
/\-\/\-\/\-\/\-\/\-\/\-\/\ Bilety należy kasować przed zejściem(ZTM
\ K...@e...eu.org / Warszawa)
/ http://epsilon.eu.org/ \
\/-/\/-/\/-/\/-/\/-/\/-/\/

do góry

Mariusz Kruk wrote:
> epsilon$ while read LINE; do echo \>"$LINE"; done < "Mariusz Kruk"
>>> Wydaje mi się, że analogiczne zadanie to najkrótszy program w
>>> Brainfucku generujący stałą (przy założeniu "non-wrapping"):
>>> http://esoteric.voxelperfect.net/wiki/Brainfuck_cons
tants
>>> Dokładna równoważność będzie chyba, jeśli zamiast "długość programu"
>>> postawimy "liczbą operacji +".
>> No, trochę nie. Brainf*ck nie ma mnożenia. Poza tym, ma odejmowanie.
>
> Wróć. Nie zauważyłem wrapping/non-wrapping. Ale uwaga o mnożeniu
> zostaje.

Mnożenie ma jako dodawanie jedynek w pętli, licznik pętli jest
inicjowany za pomocą dodawania jedynek. Np.:
15: +++[>+++++<-]>
+++ ustaw komórkę na 3
[ dopóki nie zero
> w następnej komórce (z wynikiem)
+++++ dodawaj po 5
<- zmniejsz licznik
] i sprawdź
> przechodzimy do wyniku

czyli (1+1+1)*(1+1+1+1+1)

Z tą różnicą, że w mnożenie daje narzut dodatkowych 5 znaków ([><-]),
które w problemie jedynek się nie liczą (interesuje nas tylko liczba +).

--
Paweł Kierski
n...@p...net

do góry

epsilon$ while read LINE; do echo \>"$LINE"; done < "Paweł Kierski"
>>>> Wydaje mi się, że analogiczne zadanie to najkrótszy program w
>>>> Brainfucku generujący stałą (przy założeniu "non-wrapping"):
>>>> http://esoteric.voxelperfect.net/wiki/Brainfuck_cons
tants
>>>> Dokładna równoważność będzie chyba, jeśli zamiast "długość programu"
>>>> postawimy "liczbą operacji +".
>>> No, trochę nie. Brainf*ck nie ma mnożenia. Poza tym, ma odejmowanie.
>> Wróć. Nie zauważyłem wrapping/non-wrapping. Ale uwaga o mnożeniu
>> zostaje.
> Mnożenie ma jako dodawanie jedynek w pętli, licznik pętli jest
>inicjowany za pomocą dodawania jedynek. Np.:
>15: +++[>+++++<-]>
>+++ ustaw komórkę na 3
>[ dopóki nie zero
> > w następnej komórce (z wynikiem)
>+++++ dodawaj po 5
><- zmniejsz licznik
>] i sprawdź
> > przechodzimy do wyniku

Faktycznie.

>czyli (1+1+1)*(1+1+1+1+1)
>
> Z tą różnicą, że w mnożenie daje narzut dodatkowych 5 znaków ([><-]),
>które w problemie jedynek się nie liczą (interesuje nas tylko liczba +).

No i to jest tylko rozwiązanie dla konkretnych przypadków, a nie ogólny
algorytm.

--
[------------------------] Microsoft Office 2000: Ach, jak wygodnie
[ K...@e...eu.org ]
[ http://epsilon.eu.org/ ]
[------------------------]

do góry

Mariusz Kruk pisze:

> 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).

Może tak (C++):

#define RANGE 20

int val[RANGE+1]; // na wyniki
int i,j,m;
for(i=1;i<=RANGE;i++) val[i]=i;
for(i=2;i<=RANGE;i++)
for(j=2;j<i;j++) {
if(i%j==0)
{ m=val[i/j]+val[j];
if (m<val[i]) val[i]=m;
}
if (1+val[i-1]<val[i]) val[i]=1+val[i-1];
}

for(i=1;i<=RANGE;i++)
cout << i << " " << val[i] << endl;



P.

do góry

Mariusz Kruk wrote:
[...]
>> Mnożenie ma jako dodawanie jedynek w pętli, licznik pętli jest
>> inicjowany za pomocą dodawania jedynek. Np.:
>> 15: +++[>+++++<-]>
>> +++ ustaw komórkę na 3
>> [ dopóki nie zero
>>> w następnej komórce (z wynikiem)
>> +++++ dodawaj po 5
>> <- zmniejsz licznik
>> ] i sprawdź
>>> przechodzimy do wyniku
>
> Faktycznie.
>
>> czyli (1+1+1)*(1+1+1+1+1)
>>
>> Z tą różnicą, że w mnożenie daje narzut dodatkowych 5 znaków ([><-]),
>> które w problemie jedynek się nie liczą (interesuje nas tylko liczba +).
>
> No i to jest tylko rozwiązanie dla konkretnych przypadków, a nie ogólny
> algorytm.

I dokładnie tylko tyle pierwotnie chciałem powiedzieć: problem jest
równoważny znajdowaniu takiego programu w Brainfucku, który nie korzysta
z wrappingu i ma najmniej operacji +, a daje szukaną stałą.

Te programy są najkrótsze ze względu na wszystkie operacje BF, i - jak
zauważyłeś - jest to tylko kilkadziesiąt rozwiązań.

--
Paweł Kierski
n...@p...net

do góry