prosta zagadka(procesor nie ogarnia)

swir240

2013-02-19 00:16

swir2402013-02-19 00:16

Nie wiem czy dobry dział jbc. to przenieść.

Problem wygląda następująco: znalazlem Ciekawa zagadke:

Człowiek kupił w sklepie 4 towary. Zauważył, że kasjer zamiast dodać ich ceny do siebie pomnożył je i wyszło mu 7,11 zł.
Gdy zwrócił uwagę kasjerowi, że ceny artykułów należy dodać kasjer dodał do siebie ceny towarów i znów wyszło mu 7,11 zł.

Ile kosztowały poszczególne produkty?

Zaczynając prace z C++ postanowiłem zabawić się w rozwiązanie jej prostym programem, po chwili wyszło mi coś takiego, czego mój procek nie ogarnia już po "połowie" programu.

Kopiuj

#include <iostream>
#include<cstdlib>
#include<fstream>
using namespace std;


int main()
{
int a=0,b=0,c=0,d=0,p=0,o=0,i=0;
int il[10000000],s[1000000000];


for (int i=0;i<1000;i+=4)
{
il[i+4]=a+b+c+d;
s[i+4]=a*b*c*d;
a+=1;
for(int qw=0;qw<1000;qw++)
{il[i+3]=a+b+c+d;
s[i+3]=a*b*c*d;
b+=1;
for(int qw=0;qw<1000;qw++)
{il[i+2]=a+b+c+d;
s[i+2]=a*b*c*d;
c+=1;
for(int qe=0;qe<1000;qe++)
{il[i+1]=a+b+c+d;
s[i+1]=a*b*c*d;
d+=1;
}
}
}
}

return 0;

}

Na wyświetlenie rozwiązania mam pomysł sprawdzając co pasuje do wyniku, tylko komputer trochę tego co już jest nie ogarnia.

Pytanie: Myśl techniczna jest zła? Czy teoretycznie mogło by to działać? Jakie są wasze propozycje rozwiązania?

edytowany 1x, ostatnio: ŁF 2016-12-13 17:26

ŁF 2013-02-19 15:20

na przyszłość nadawaj wątkom bardziej ambitne tematy i formatuj kod

fasadin

2013-02-19 00:27

~~fasadin~~2013-02-19 00:27

Rejestracja:ponad 13 lat
Ostatnio:prawie 3 lata
Postów:4882

moja pierwsza propozycja to kod formatuj i koloruj (wstawiaj w znaczniki code) bo mój mózg nie ogarnia tego co napisałeś.

Widzę tylko, że zadeklarowałeś 10 milionową tablicę intów oraz niewiele większą bo tylko MILIARDOWĄ tablice intów. Hmm policzmy dla przypadku int zajmuje 4 bajty

10 000 000 * 4B + 1 000 000 000 * 4B = 4 040 000 000 B
no to zamienimy to ma megaBajty więc dziele przez milion i wychodzi (uwaga)
4040 MB! Gratulacje, mimo, że kupowałem kompa półtora roku temu nawet moja pamięć by tego nie przydzieliła (4GB).

więc podsumujmy

nie znasz architektury komputera (procesor? poważnie?)
nie masz pojęcia o stosie i stercie.
Twój algorytm zapewne jest do kitu skoro potrzebuje 4 GB ramu.
Nie formatujesz kodu dla jedynie czterech wewnętrznych forów
Zamieszczasz kod na forum i nie dbasz o to że ktoś kto chcę pomóc będzie musiał patrzeć na tą masakrę.
nazywasz zmienne tak, że może po 10 minutach patrzenia w to "coś" będzie wiadomo co za co robi.

ah no tak, pominąłem ostatnią drobnostkę. Pętla wykonuję się jedynie miliard razy...

edytowany 2x, ostatnio: ~~fasadin~~ 2013-02-19 00:29

Shalom

2013-02-19 00:28

~~Shalom~~2013-02-19 00:28

Rejestracja:około 21 lat
Ostatnio:prawie 3 lata
Lokalizacja:Space: the final frontier
Postów:26433

int il[10000000],s[1000000000];

Brawo, zaalokowałeś właśnie 4,04 GB pamięci ram. Po co ty w ogóle to tablicujesz? o_O
Ja bym przyjął takie założenia:
abcd = 711
a+b+c+d = 711
1 <= a,b,c,d < 708
Jak już chcesz puszczać bruta to z głową. Zauważ na przykład że jeśli a = 10 to bc*d=71,1 czyli b,c,d muszą być mniejsze od 72. Widzisz wiec chyba ze puszczanie tutaj każdej pętli od 1 do 1000 nie ma sensu? ;)
Istnieją języki które wspierają "constraint programming" dzięki którym można takie równania rozwiązać w mgnieniu oka.

Krycho

2013-02-19 00:28

Krycho2013-02-19 00:28

Rejestracja:prawie 14 lat
Ostatnio:ponad 2 lata
Postów:353

Nie chce mi sie nawet poprawnosci rozwiazania sprawdzac, ale na pierwszy rzut oka widze ze i tak nie przejdzie. Druga tablica intow ma 1 000 000 000 elementow. Liczac na szybko bedzie to jakies 3.7GB pamieci(poprawcie jesli sie myle). Pierwsza rzecz, ze w ogole probujesz nawet pierwsza tablice zadeklarowac na stosie. Samo to juz jestem pewien spowoduje stack overflow. Proba zadeklarowania na stercie tak czy tak 3.7GB nie przejdzie bo wywali bad alloc. Po prostu to jest za duzo. Pomysl nad optymalniejszym rozwiazaniem.

@Shalom
Kurde 22 sek szybszy xD

Widze obydwoje zaokraglacie wynik ;p

edytowany 3x, ostatnio: Krycho 2013-02-19 00:31

swir240

2013-02-19 01:34

swir2402013-02-19 01:34

zrozumiałem błąd, i jeszcze bardziej mi to skomplikowało kwestie rozwiązania....

szopenfx

2013-02-19 02:30

szopenfx2013-02-19 02:30

Rejestracja:prawie 21 lat
Ostatnio:4 miesiące

skasowanie tablicy i zrobienie porównania to ta kwestia "komplikacji"? w ogóle nie miałeś warunku porównania wyniku mnożenia z dodawaniem wystarczy przerwać pętle jeśli oba wyniki są sobie równe i wynoszą 711 i wypisać poszczególne "ceny".
Ostatnią cenę d możesz wyliczyć na podstawie wzoru:
d = 711 - (a + b + c)
Kolejna sprawa - wiesz, że na pewno jedna z liczb musi być nieparzysta bo wynik mnożenia jest taką liczbą, więc można przyjąć, że np. zmienna a będzie kolejną liczbą nieparzystą. Masz więc po tych ulepszeniach około:
355 iteracji a, 711 iteracji b, i 711 iteracji c, d wyliczane z automatu.
W praktyce odnajdziesz te ceny znacznie szybciej, gdy porzucisz iterowanie jeśli wynik mnożenia liczb przekroczy 711 wiadomo, że kolejne będą już tylko większe więc po co niepotrzebnie wypalać prąd?

Azarien

2013-02-19 11:40

Azarien2013-02-19 11:40

Rejestracja:ponad 21 lat
Ostatnio:około 3 godziny

50 zł :-)

Kopiuj

#include <stdio.h>
#include <conio.h>

int main()
{
    for (int a=1; a<=708; a++)
    {
        for (int b=1; b<=708; b++)
        {
            if (a+b > 709)
                break;
            for (int c=1; c<=708; c++)
            {
                if (a+b+c > 710)
                    break;
                for (int d=1; d<=708; d++)
                {
                    if (a+b+c+d > 711)
                        break;
                    if (a+b+c+d == 711 && a*b*c*d == 711000000)
                    {
                        printf("%.2f %.2f %.2f %.2f", (float)a/100, (float)b/100, (float)c/100, (float)d/100);
                        _getch();
                        goto fin;
                    }
                }
            }
        }
    }
    fin:
    return 0;
}

edytowany 4x, ostatnio: Azarien 2013-02-19 13:39

Zobacz pozostałe 5 komentarzy

Azarien 2013-02-19 13:39

poprawiłem błąd (teoretyczny, bo nie ma wpływu na wynik)

_13th_Dragon 2013-02-19 14:22

@Azarien, dawanie przykładów z goto ... <ciach><ciach><ciach>

Azarien 2013-02-19 14:58

czep się ;-)

somekind 2013-02-21 21:47

Grosze w potędze? A co się za to kupi? ;)

_13th_Dragon 2013-02-21 22:40

Za to się nie kupuje, za to się pieski grzebie, przecież @nemomemo wyraźnie napisał. ;)

vpiotr

2013-02-19 12:16

~~vpiotr~~2013-02-19 12:16

Rejestracja:ponad 13 lat
Ostatnio:prawie 3 lata

A to nie powinno być jakoś policzone algebrą liniową?

Shalom

2013-02-19 12:41

~~Shalom~~2013-02-19 12:41

Rejestracja:około 21 lat
Ostatnio:prawie 3 lata
Lokalizacja:Space: the final frontier
Postów:26433

Myśle że najprościej tak:
http://www.mozart-oz.org/documentation/fdt/node15.html#section.problem.money
;)

Lena(R)

2013-02-19 13:37

Lena(R)2013-02-19 13:37

Rejestracja:około 14 lat
Ostatnio:ponad 4 lata
Postów:98

Krycho napisał(a):

Proba zadeklarowania na stercie tak czy tak 3.7GB nie przejdzie bo wywali bad alloc.

Czy ja o czymś nie wiem, czy to co napisałeś nie jest prawdą? Jeśli ja mam 8 GB pamięci, to nie mogę za alokować jakichś marnych 3,7 GB? No weźcie mnie oświećcie, bo nie usnę dzisiaj...:P

Patryk27 2013-02-19 13:41

Windows nie ma przypadkiem limitów pamięci RAM per proces?

~~fasadin~~ 2013-02-19 13:43

mało tego użytkownik próbował zadeklarować na stosie a nie na stercie.

_13th_Dragon 2013-02-19 13:44

Pewnie mowa o 32-bitowych znaleziskach archeologicznych.

Lena(R) 2013-02-19 14:00

Pewnie Krycho miał na myśli 32-bitowy system, a ja zapomniałem zupełnie o tym ograniczeniu. Zdarza się.

Bartosz Wójcik

2013-02-19 13:39

Bartosz Wójcik2013-02-19 13:39

Rejestracja:ponad 14 lat
Ostatnio:ponad 4 lata
Postów:439

Pythonowy solver z3py

Kopiuj

a, b, c, d = Reals('a b c d')

set_option(precision=3)

solve(a > 0, b > 0, c > 0, d > 0, a + b + c + d == 7.11, a * b * c * d == 7.11,
      show=True)

http://rise4fun.com/Z3Py/ycsW

mówi

Kopiuj

Problem:
[a > 0,
 b > 0,
 c > 0,
 d > 0,
 a + b + c + d = 711/100,
 a·b·c·d = 711/100]
Solution:
[b = 1, c = 2, d = 1.237?, a = 2.872?]

Zobacz pozostałe 3 komentarze

Bartosz Wójcik 2013-02-19 14:02

może jeszcze dopiszcie, że takich cen nie ma w Realu tylko w Lidlu... ;)

sig 2013-02-19 14:07

mi z tych wyników wyszła suma 7.109 a mnożenie 7.105328, więc to dalej nie to

_13th_Dragon 2013-02-19 14:24

No bo wypisało tylko z 3ma znakami ...

Azarien 2013-02-19 15:00

i dlatego trzeba było liczyć na groszach...

sig 2013-02-19 15:59

No właśnie, 3-go miejsca po przecinku akurat to zadanie nie uznaje na żadnym etapie obliczeń.

Azarien

2013-02-19 15:52

Azarien2013-02-19 15:52

Rejestracja:ponad 21 lat
Ostatnio:około 3 godziny

Kopiuj

using System;
using Microsoft.SolverFoundation.Services;

class Program
{
    static void Main()
    {
        SolverContext context = SolverContext.GetContext();
        Model model = context.CreateModel();
        Decision a = new Decision(Domain.IntegerNonnegative, null);
        Decision b = new Decision(Domain.IntegerNonnegative, null);
        Decision c = new Decision(Domain.IntegerNonnegative, null);
        Decision d = new Decision(Domain.IntegerNonnegative, null);
        model.AddDecisions(a, b, c, d);
        model.AddConstraint(null, a + b + c + d == 711);
        model.AddConstraint(null, a * b * c * d == 711000000);
        context.Solve();
        Console.WriteLine(a.GetDouble() / 100);
        Console.WriteLine(b.GetDouble() / 100);
        Console.WriteLine(c.GetDouble() / 100);
        Console.WriteLine(d.GetDouble() / 100);
        Console.ReadKey();
    }
}

Oak

2013-02-19 17:58

Oak2013-02-19 17:58

Rejestracja:ponad 13 lat
Ostatnio:prawie 10 lat
Postów:95

Kopiuj

solutions = [ (a,b,c,d) | a <- [1..711],
                          b <- [a..711-a],
                          c <- [b..711-(a+b)],
                          let d = 711-(a+b+c),
                          d > c,
                          a*b*c*d == 711000000 ]

main = print solutions

-- wynik (w groszach):
-- [(120,125,150,316)]

~~vpiotr~~ 2013-02-19 20:02

Przydałoby się podać w jakim to środowisku. Python? Matlab? R?

Azarien 2013-02-19 20:10

wygląda na Haskell

Oak 2013-02-19 20:28

tak, to Haskell.

Liczba odpowiedzi na stronę

Treść *

Treść

Podgląd

Kliknij, aby dodać treść...

Kliknij, aby dodać załącznik lub wklej ze schowka.

Instrukcja obsługi Markdown

Pomoc 1.18.8

Typografia

Edytor obsługuje składnie Markdown, w której pojedynczy akcent *kursywa* oraz _kursywa_ to pochylenie. Z kolei podwójny akcent **pogrubienie** oraz __pogrubienie__ to pogrubienie. Dodanie znaczników ~~strike~~ to przekreślenie.

Możesz dodać formatowanie komendami , , oraz .

Ponieważ dekoracja podkreślenia jest przeznaczona na linki, markdown nie zawiera specjalnej składni dla podkreślenia. Dlatego by dodać podkreślenie, użyj underline.

Komendy formatujące reagują na skróty klawiszowe: Ctrl+B, Ctrl+I, Ctrl+U oraz Ctrl+S.

Linki

By dodać link w edytorze użyj komendy lub użyj składni [title](link). URL umieszczony w linku lub nawet URL umieszczony bezpośrednio w tekście będzie aktywny i klikalny.

Jeżeli chcesz, możesz samodzielnie dodać link: <a href="link">title</a>.

Wewnętrzne odnośniki

Możesz umieścić odnośnik do wewnętrznej podstrony, używając następującej składni: [[Delphi/Kompendium]] lub [[Delphi/Kompendium|kliknij, aby przejść do kompendium]]. Odnośniki mogą prowadzić do Forum 4programmers.net lub np. do Kompendium.

Wspomnienia użytkowników

By wspomnieć użytkownika forum, wpisz w formularzu znak @. Zobaczysz okienko samouzupełniające nazwy użytkowników. Samouzupełnienie dobierze odpowiedni format wspomnienia, zależnie od tego czy w nazwie użytkownika znajduje się spacja.

Znaczniki HTML

Dozwolone jest używanie niektórych znaczników HTML: <a>, , , <kbd>, <del>, , <dfn>, <pre>, <blockquote>, <hr/>, ,  oraz <img/>.

Skróty klawiszowe

Dodaj kombinację klawiszy komendą notacji klawiszy lub skrótem klawiszowym Alt+K.

Reprezentuj kombinacje klawiszowe używając taga <kbd>. Oddziel od siebie klawisze znakiem plus, np <kbd>Alt+Tab</kbd>.

Indeks górny oraz dolny

Przykład: wpisując H2O i m2 otrzymasz: H₂O i m².

Składnia Tex

By precyzyjnie wyrazić działanie matematyczne, użyj składni Tex.

<tex>arcctg(x) = argtan(\frac{1}{x}) = arcsin(\frac{1}{\sqrt{1+x^2}})</tex>

Kod źródłowy

Krótkie fragmenty kodu

Wszelkie jednolinijkowe instrukcje języka programowania powinny być zawarte pomiędzy obróconymi apostrofami: `kod instrukcji` lub ``console.log(`string`);``.

Kod wielolinijkowy

Dodaj fragment kodu komendą . Fragmenty kodu zajmujące całą lub więcej linijek powinny być umieszczone w wielolinijkowym fragmencie kodu. Znaczniki ``` lub ~~~ umożliwiają kolorowanie różnych języków programowania. Możemy nadać nazwę języka programowania używając auto-uzupełnienia, kod został pokolorowany używając konkretnych ustawień kolorowania składni:

```javascript document.write('Hello World'); ```

Możesz zaznaczyć również już wklejony kod w edytorze, i użyć komendy by zamienić go w kod. Użyj kombinacji Ctrl+`, by dodać fragment kodu bez oznaczników języka.

Tabelki

Dodaj przykładową tabelkę używając komendy . Przykładowa tabelka składa się z dwóch kolumn, nagłówka i jednego wiersza.

Wygeneruj tabelkę na podstawie szablonu. Oddziel komórki separatorem ; lub |, a następnie zaznacz szablonu.

nazwisko;dziedzina;odkrycie
Pitagoras;mathematics;Pythagorean Theorem
Albert Einstein;physics;General Relativity
Marie Curie, Pierre Curie;chemistry;Radium, Polonium

Użyj komendy by zamienić zaznaczony szablon na tabelkę Markdown.

Lista uporządkowana i nieuporządkowana

Możliwe jest tworzenie listy numerowanych oraz wypunktowanych. Wystarczy, że pierwszym znakiem linii będzie * lub - dla listy nieuporządkowanej oraz 1. dla listy uporządkowanej.

Użyj komendy by dodać listę uporządkowaną.

1. Lista numerowana
2. Lista numerowana

Użyj komendy by dodać listę nieuporządkowaną.

* Lista wypunktowana
* Lista wypunktowana
** Lista wypunktowana (drugi poziom)

Składnia Markdown

Edytor obsługuje składnię Markdown, która składa się ze znaków specjalnych. Dostępne komendy, jak formatowanie , dodanie tabelki lub fragmentu kodu są w pewnym sensie świadome otaczającej jej składni, i postarają się unikać uszkodzenia jej.

Dla przykładu, używając tylko dostępnych komend, nie możemy dodać formatowania pogrubienia do kodu wielolinijkowego, albo dodać listy do tabelki - mogłoby to doprowadzić do uszkodzenia składni.

W pewnych odosobnionych przypadkach brak nowej linii przed elementami markdown również mógłby uszkodzić składnie, dlatego edytor dodaje brakujące nowe linie. Dla przykładu, dodanie formatowania pochylenia zaraz po tabelce, mogłoby zostać błędne zinterpretowane, więc edytor doda oddzielającą nową linię pomiędzy tabelką, a pochyleniem.

Skróty klawiszowe

Skróty formatujące, kiedy w edytorze znajduje się pojedynczy kursor, wstawiają sformatowany tekst przykładowy. Jeśli w edytorze znajduje się zaznaczenie (słowo, linijka, paragraf), wtedy zaznaczenie zostaje sformatowane.

Ctrl+B - dodaj pogrubienie lub pogrub zaznaczenie
Ctrl+I - dodaj pochylenie lub pochyl zaznaczenie
Ctrl+U - dodaj podkreślenie lub podkreśl zaznaczenie
Ctrl+S - dodaj przekreślenie lub przekreśl zaznaczenie

Notacja Klawiszy

Alt+K - dodaj notację klawiszy

Fragment kodu bez oznacznika

Alt+C - dodaj pusty fragment kodu

Skróty operujące na kodzie i linijkach:

Alt+L - zaznaczenie całej linii
Alt+, Alt+ - przeniesienie linijki w której znajduje się kursor w górę/dół.
Tab/⌘+] - dodaj wcięcie (wcięcie w prawo)
Shit+Tab/⌘+[ - usunięcie wcięcia (wycięcie w lewo)

Dodawanie postów:

Ctrl+Enter - dodaj post
⌘+Enter - dodaj post (MacOS)

prosta zagadka(procesor nie ogarnia)

swir240

fasadin

Shalom

swir240

vpiotr

Shalom

Krycho napisał(a):

Smileys & People

Animals & Nature

Food & Drink

Travel & Places

Activities

Objects

Symbols

Typografia

Linki

Wewnętrzne odnośniki

Wspomnienia użytkowników

Znaczniki HTML

Skróty klawiszowe

Indeks górny oraz dolny

Składnia Tex

Kod źródłowy

Krótkie fragmenty kodu

Kod wielolinijkowy

Tabelki

Lista uporządkowana i nieuporządkowana

Składnia Markdown

Skróty klawiszowe