eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingRozkład na jedynki
Ilość wypowiedzi w tym wątku: 10

  • 1. Data: 2009-01-22 21:41:27
    Temat: Rozkład na jedynki
    Od: Mariusz Kruk <M...@e...eu.org>

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


  • 2. Data: 2009-01-22 22:02:39
    Temat: Re: Rozkład na jedynki
    Od: Piotrne <p...@p...onet.pl>

    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.


  • 3. Data: 2009-01-22 22:23:54
    Temat: Re: Rozkład na jedynki
    Od: Mariusz Kruk <M...@e...eu.org>

    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/\.\
    .\.\.\.\.\.\.\.\.\.\.\.\.\.


  • 4. Data: 2009-01-23 11:42:03
    Temat: Re: Rozkład na jedynki
    Od: Paweł Kierski <n...@p...net>

    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


  • 5. Data: 2009-01-23 11:45:31
    Temat: Re: Rozkład na jedynki
    Od: Mariusz Kruk <M...@e...eu.org>

    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/ ]
    [------------------------]


  • 6. Data: 2009-01-23 11:46:20
    Temat: Re: Rozkład na jedynki
    Od: Mariusz Kruk <M...@e...eu.org>

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


  • 7. Data: 2009-01-23 12:12:54
    Temat: Re: Rozkład na jedynki
    Od: Paweł Kierski <n...@p...net>

    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


  • 8. Data: 2009-01-23 12:44:37
    Temat: Re: Rozkład na jedynki
    Od: Mariusz Kruk <M...@e...eu.org>

    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/ ]
    [------------------------]


  • 9. Data: 2009-01-23 13:23:25
    Temat: Re: Rozkład na jedynki
    Od: Piotrne <p...@p...onet.pl>

    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.


  • 10. Data: 2009-01-23 13:56:49
    Temat: Re: Rozkład na jedynki
    Od: Paweł Kierski <n...@p...net>

    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

strony : [ 1 ]


Szukaj w grupach

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: