Podział prostokąta na kwadraty

damkur88 · Post autor: **damkur88** » 29 mar 2011, o 14:35

Witam, mam taki problem a mianowicie napisanie programu który po zadaniu wymiarów płyty oraz wymiaru kwadratu program podzieli płytę na n możliwych kwadratów chodzi o to aby był jak najmniejszy odpad. Nie chodzi mi o konkretny program napisany w konkretnym języku tylko o algorytm rozwiązujący ten problem.

Np. wymiary płyty(format A4 tj. 210 x 297 mm) oraz wymiar boku kwadratu to np. 10mm. Ile zmieści się w nim kwadracików hmm jak napisać algorytm dla programu np. C++:?:

Proszę o pomoc i z góry dziękuję

Errichto · Post autor: **Errichto** » 29 mar 2011, o 14:55

Po pierwsze zdecyduj się z czym masz problem, bo:

Nie chodzi mi o konkretny program napisany w konkretnym języku tylko o algorytm rozwiązujący ten problem.
[...]
jak napisać algorytm dla programu np. C++

Po drugie chyba źle sformułowałeś pytanie.
Zapewne chodzi Ci o wyznaczenie \(\displaystyle{ n}\) dającego najmniejszy odpad (czyli też największego możliwego \(\displaystyle{ n}\) - wiesz dlaczego tek jest?). Bo z tego co piszesz, wynika że masz już \(\displaystyle{ n}\) - więc co jeszcze chcesz zrobić?
Jeśli masz wyznaczyć \(\displaystyle{ n}\), to zastanów się ile kwadratów wchodzi wszerz, ile wzdłuż i wymnóż te 2 liczby.

damkur88 · Post autor: **damkur88** » 29 mar 2011, o 17:34

Chciałem sobie zrobić taki program uniwersalny, który po podaniu danej-długości boku kwadratu, program da mi informacje o wyniku tj. ile będzie kwadratów na płycie

Errichto · Post autor: **Errichto** » 29 mar 2011, o 17:48

Rozumiem, że na wejściu podajesz też wymiary płyty?

Rozwiązanie tego jest właśnie w poście wyżej.

damkur88 · Post autor: **damkur88** » 29 mar 2011, o 17:53

Dokładnie podaje dane płyty i kwadratu reszta robi program, postaram się coś wykombinować...

Errichto · Post autor: **Errichto** » 29 mar 2011, o 18:04

Zastanów się.
Masz np. szerokość 17.
To ile wszerz wejdzie kwadratów o boku 5?

damkur88 · Post autor: **damkur88** » 29 mar 2011, o 18:32

Więcej jak 3 kwadraty nie wejdą

Errichto · Post autor: **Errichto** » 29 mar 2011, o 18:35

I jak to wyliczyłeś?

damkur88 · Post autor: **damkur88** » 29 mar 2011, o 18:55

17:5=3.4

Errichto · Post autor: **Errichto** » 29 mar 2011, o 19:08

No dokładnie.
W c++ coś takiego:
\(\displaystyle{ 17/5}\)
da Ci wynik \(\displaystyle{ 3}\) - od razu bez ułamka (pod warunkiem, że pracujesz na intach, nie ma potrzeby tutaj double używać).
Także wszerz zmieści się \(\displaystyle{ x/a}\)
Wzdłuż, jak się już zapewne domyślasz \(\displaystyle{ y/a}\)
Gdy pomnożysz te 2 liczby, otrzymasz szukaną ilość płytek.

damkur88 · Post autor: **damkur88** » 29 mar 2011, o 20:00

Dzięki biorę się za napisanie programu