prosta zagadka(procesor nie ogarnia)

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.

#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?

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

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.

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

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

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?

50 zł :-)

#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;
}

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

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

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

Pythonowy solver z3py

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

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?]

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();
    }
}

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