Zobacz pełną wersję : Matematyka, elektronika i programowanie czyli mały problem- wielka sprawa
kamilkamien
06-08-2010, 15:50
Nie bardzo wiem jak to zacząć a opisanie tej pierdołki nie jest za proste.
Zwracam się z pytaniem/prośba do osób mających do czynienia z elektroniką, matematyką i programowaniem. Potrzebuje liczydełko elektroniczne ale nie jest to takie proste jak by się mogło wydawać z pozoru. Chodzi o to, aby program tylko dopasowywał odpowiednie zestawy liczb i dodawał tak aby wychodziły pełne tysiące w wynikach działań.
Przykładowo w statystyce mam zestaw liczb
250
138
112
150
2500
380
600
i trzeba je szybko tak dopasować aby wynikiem był pełen tysiąc czyli
250+ 150+ 600= 1000
a liczby 123 112 380 2500 odpadają
Sprawa wygląda dość prosto jeśli do dyspozycji mamy 7 liczb ale jeśli dana statystyka opiewa na 30 liczb to kombinacji jest baaardzo wiele.
Czy idzie coś takiego napisać w jakimś programie aby samem zliczało, wybierało i dodawało otrzymując pełne tysiące z podanych liczb w zbiorze?
No to nawet umiarkowanie rozgarnięty programista jest w stanie machnąć w 20min, generalnie. ;)
kamilkamien
06-08-2010, 17:24
No to nawet umiarkowanie rozgarnięty programista jest w stanie machnąć w 20min, generalnie. ;)
A znasz takiego? Wielu się na forum deklarowało programistów ale nie znam nikogo, kto by potrafił sie tym zająć
Zanim ktoś się weźmie za pisanie, pytania dodatkowe:
- czy w danym zbiorze liczb może istnieć większa od 1 ilość podzbiorów dających 1000? co wtedy - wskazać pierwszy znaleziony (dowolny, czy optymalny pod jakimś względem, np. najmniej składników), czy wypisać wszystkie?
- jaka jest maksymalna ilość danych?
Zanim ktoś się weźmie za pisanie, pytania dodatkowe:
1 czy w danym zbiorze liczb może istnieć większa od 1 ilość podzbiorów dających 1000? co wtedy - wskazać pierwszy znaleziony (dowolny, czy optymalny pod jakimś względem, np. najmniej składników), czy wypisać wszystkie?
2 jaka jest maksymalna ilość danych?
Pytanie 2 powinno raczej brzmieć: Czy ilość liczb wejściowych jest stała.
Zadanko jest ciekawsze, jeśli na pyt. 1 odpowiedź brzmi "Tak, i należy wskazać wszystkie" ;-)
kamilkamien
06-08-2010, 17:55
Zanim ktoś się weźmie za pisanie, pytania dodatkowe:
- czy w danym zbiorze liczb może istnieć większa od 1 ilość podzbiorów dających 1000? co wtedy - wskazać pierwszy znaleziony (dowolny, czy optymalny pod jakimś względem, np. najmniej składników), czy wypisać wszystkie?
- jaka jest maksymalna ilość danych?
Aby było łatwiej to od końca. Maksymalna ilość danych to 30.
Jeśli chodzi o pierwsze pytanie, to najlepiej aby wypisane były wszystkie dostępne rozwiązania ale bez powtórzeń biorąc pod uwagę składniki działania czyli prościej to tak jak by liczby spisać na kartkach i ułożyć wszystkie na stole. Działania dające "pełnotysieczne" wyniki odkładamy w oddzielne miejsce np. na krześle i kolejne tworzymy z pozostałych dostępnych jeszcze na stole kartkach. Chodzi o zastosowanie kombinatoryki bez powtórzeń.
To jak tak troche OFFTOPOWO. Wyglada to jak liczenie punktow z jakiegos konkursu. Winiary chyba cos kiedys takiego zrobilo. Liczby i ich sumy byly takie...ze nikt nie wygrywal. Wiec jesli to cos takiego, to dalbym sobie spokoj.
algorytm szukania jest prosty, ale nie wiem na ile efektywny
1. wygenerować wszystkie możliwe kombinacje od 1 do n elementów (n ilość danych wejściowych)
2. zsumować każdą kombinację
3. sumę podzielić modulo 1000
jeśli reszta z dzielenia 0 to trafione
jeśli reszta z dzielenia różna od 0 to pudło
dla każdego n ilość kombinacji
https://forum.nikoniarze.pl//brak.gif
źródło (http://img835.imageshack.us/img835/2870/rownanie.jpg) a to się równa 2^n, przy n=30 daje to "tylko" 1 073 741 824
jeśli wystarczyłaby jedna kombinacja to wtedy troszkę zmieniamy:
1 generujemy kombinację
2 sumujemy ją
3. suma mod 1000
jeśli reszta z dzielenia 0 to trafione znalezione
jeśli reszta z dzielenia różna od 0 to pudło i wracamy do 1
Proszę bardzo, poniżej programik w PHP który działa wg algorytmu kolegi ksviper. Napisany szybko na kolanie, pewnie można byłoby go zoptymalizować, albo wykorzystać jakiś szybszy język.
Dla 20 liczb program działa na moim komputerze ok. 30 sekund. Pytanie - ile czasu będzie działał dla 30 liczb? :)
<?php
$inp[0] = 250;
$inp[1] = 138;
$inp[2] = 112;
$inp[3] = 150;
$inp[4] = 2500;
$inp[5] = 380;
$inp[6] = 600;
$inp[7] = 601;
$inp[8] = 602;
$inp[9] = 603;
$inp[10] = 604;
$inp[11] = 101;
$inp[12] = 102;
$inp[13] = 6;
$inp[14] = 7;
$inp[15] = 8;
$inp[16] = 9;
$inp[17] = 10;
$inp[18] = 12;
$inp[19] = 50;
$a = 1;
$cnt = count($inp);
while ($a < pow(2, $cnt))
{
$sum = 0;
$result = "";
$binstring = str_pad(decbin($a), $cnt, '0', STR_PAD_LEFT);
for($i = 0; $i < $cnt; $i++) {
if ($binstring[$i] == 1) {
$sum += $inp[$i];
$result .= ' + ' . $inp[$i];
}
}
$result .= ' = ' . $sum . "\n<br>";
if (fmod($sum, 1000) == 0)
echo $result;
$a++;
}
?>
I jeszcze wynik działania dla liczb podanych przez autora:
+ 138 + 112 + 150 + 600 = 1000
+ 250 + 150 + 600 = 1000
+ 250 + 138 + 112 + 2500 = 3000
PS: machnięte (razem z testem) w 20 minut, cieszę się że jestem umiarkowanie rozgarniętym programistą :-)
PS: machnięte (razem z testem) w 20 minut, cieszę się że jestem umiarkowanie rozgarniętym programistą :-)
Ee-e; Programistą od razu.
Koderem, co najwyżej ;)
Miałeś gotowy algorytm. To kolega wcześniej się wykazał.
Zaproponuj algorytm bardziej optymalny od tego :)
Ee-e; Programistą od razu.
Koderem, co najwyżej ;)
Też dobrze, bo w pracy robię teraz co innego, nie kodowałem już od dawna :-)
Miałeś gotowy algorytm. To kolega wcześniej się wykazał.
Zaproponuj algorytm bardziej optymalny od tego :)
Obawiam się, że nie ma. Gdyby operacja dodawania była kosztowna, to można byłoby się bawić w optymalizacje przez:
- sprawdzanie przed sumowaniem czy suma ostatnich cyfr jest wielokrotnością 10-tki (jeżeli nie jest - nie ma co dodawać)
- przechowywanie sum częściowych dla pewnych elementów (taki cache)
Ale to może tylko trochę przyspieszyć liczenie - natomiast nie zmienia sprawy, że trzeba przejść 2^n kroków, gdzie n jest liczebnością zbioru wejściowego...
Zaproponuj algorytm bardziej optymalny od tego :)
Obawiam się, że nie ma.
Oj mylicie się, ale ja Was naprowadzę - elektronik, programista i matematyk z doskoku :)
Zarzucę wędkę - problem ten znany jest pod nazwą problemu plecakowego (http://www.porombka.pl/projects_data/prg_11/Documentation11.pdf). Programować dzisiaj mi się nie chce, robiłem kiedyś ten problem na zajęciach na uczelni.
Ale nasuwa się kilka pytań:
1) co zrobić, kiedy możliwych kombinacji rozwiązań (w postaci k zbiorów liczb sumujących się do 1000) jest więcej, przy czym jedna kombinacja rozwiązań daje n zbiorów, a inna m no i n < m. Wtedy możemy uzyskać różne ilości rozwiązań w zależności od wariantu. Jeśli punkt startowy jest losowy to mamy szansę uzyskać z (niekoniecznie) jednakowym prawdopodobieństwem każde rozwiązanie dla tego samego zbioru danych, jeśli punkt wejścia jest zawsze ten sam, to dostaniemy powtarzalność tych samych rozwiązań.
2) jeśli nie ma prawidłowego rozwiązania? W sumie to wtedy mamy puste wyjście - niby proste, ale nie zawsze - np. wydawanie reszty.
Ciekawe, może dałoby się zatrudnić do tego algorytm genetyczny? Choć zadanie jest z klasy zadań, których nie powinno się rozwiązywać tą metodą.
lekterus
06-08-2010, 23:09
Zaproponuj algorytm bardziej optymalny od tego :)
Wybacz ale musze zareagowac...BARDZIEJ OPTYMALNY ?!?! Jak cos moze byc BARDZIEJ OPTYMALNE ?? :P
Wybacz ale musze zareagowac...BARDZIEJ OPTYMALNY ?!?! Jak cos moze byc BARDZIEJ OPTYMALNE ?? :P
http://pl.wikipedia.org/wiki/Optymalizacja_oprogramowania_%28informatyka%29
co do programu stasio: co robi ta linijka i w jaki sposób?
$binstring = str_pad(decbin($a), $cnt, '0', STR_PAD_LEFT);
znalazłem na necie funkcję znajdowania wszystkich kombinacji bez powtórzeń ale nie wiem jaka jest jej złożoność obliczeniowa
function array_power_set($array) {
$results = array(array());
foreach ($array as $element)
foreach ($results as $combination)
array_push($results, array_merge(array($element), $combination));
return $results;
}
przykład zastosowania:
$set = array('a', 'b', 'c', 'd');
foreach (array_power_set($set) as $combination) {
print implode(null, $combination) . PHP_EOL;
}
Jeśli chodzi o pierwsze pytanie, to najlepiej aby wypisane były wszystkie dostępne rozwiązania ale bez powtórzeń biorąc pod uwagę składniki działania czyli prościej to tak jak by liczby spisać na kartkach i ułożyć wszystkie na stole. Działania dające "pełnotysieczne" wyniki odkładamy w oddzielne miejsce np. na krześle i kolejne tworzymy z pozostałych dostępnych jeszcze na stole kartkach. Chodzi o zastosowanie kombinatoryki bez powtórzeń.
Teraz to doczytałem i mam pytanie: co ma decydować jak jest kolejność sprawdzania liczb?
Bo np. z podanych przez Ciebie liczb jak pokazał kolega stasio to są takie kombinacje:
138 + 112 + 150 + 600 = 1000
250 + 150 + 600 = 1000
250 + 138 + 112 + 2500 = 3000
I teraz spójrz na pierwsze rozwiązanie. Jeśli je weźmiemy jako pierwsze to dwa pozostałe odpadają bo braknie nam tych cyfr do kolejnych mimo, że są poprawne. Więc jak to jest z kolejnością pobierania liczb do kombinacji (sum)?
Nasuwają się jeszcze 10 pytania:
3) Czy szukamy największej liczby rozwiązań, czy najmniejszej?
4) Szukamy rozwiązania maksymalnego czy minimalnego (w sensie sumy) - na przykład, mamy wśród liczby takie dwa podzbiory, że każdy sumuje się do 1000, ale jak zsumujemy te dwa zbiory to otrzymamy 2000 i też zbiór będący sumą elementów tych zbiorów będzie poprawny - ale w pierwszym przypadku otrzymamy dwa rozwiązania (mniejsze), a w drugim jedno (ale większe).
kamilkamien
07-08-2010, 08:59
To jak tak troche OFFTOPOWO. Wyglada to jak liczenie punktow z jakiegos konkursu. Winiary chyba cos kiedys takiego zrobilo. Liczby i ich sumy byly takie...ze nikt nie wygrywal. Wiec jesli to cos takiego, to dalbym sobie spokoj.
No na to bym raczej nie wpadł ale później zagłębie się w tym temacie. :) Znając życie, takie "loterie fantowe" do niczego nigdy nie doprowadzą :)
I teraz spójrz na pierwsze rozwiązanie. Jeśli je weźmiemy jako pierwsze to dwa pozostałe odpadają bo braknie nam tych cyfr do kolejnych mimo, że są poprawne. Więc jak to jest z kolejnością pobierania liczb do kombinacji (sum)?
Chodzi głównie o to, aby powtórzeń nie było w wykorzystanych do sumowania liczb. Kombinowanie z tym czy chcemy mieć 1000 czy np 3000 bo tak też wyjdzie nie ma znaczenia. Chodzi o dopasowanie pierwszej lepszej pary, oddzielenie jej i szukanie kolejnej z liczb pozostałych.
Nasuwają się jeszcze 10 pytania:
3) Czy szukamy największej liczby rozwiązań, czy najmniejszej?
4) Szukamy rozwiązania maksymalnego czy minimalnego (w sensie sumy) - na przykład, mamy wśród liczby takie dwa podzbiory, że każdy sumuje się do 1000, ale jak zsumujemy te dwa zbiory to otrzymamy 2000 i też zbiór będący sumą elementów tych zbiorów będzie poprawny - ale w pierwszym przypadku otrzymamy dwa rozwiązania (mniejsze), a w drugim jedno (ale większe).
3) Poszukiwana jest największa liczba rozwiązań
4) Na zestawie kilkunastu liczb chodzi o to aby wynik był tym "mniejszym" a dodać powstałe sumy "pełne", że tak sie wyrażę, można już manualnie aby nie komplikować pracy.
Swoją drogą, trochę odpuściłem wczoraj po napisaniu tego wątku, bo najzwyczajniej nie myślałem, że on się tak rozwinie. Już w tym momencie dziekuję za dotychczasową pomoc, pomijając pewne sprawy których nie do końca rozumiem z programowaniem.
Chodzi głównie o to, aby powtórzeń nie było w wykorzystanych do sumowania liczb. Kombinowanie z tym czy chcemy mieć 1000 czy np 3000 bo tak też wyjdzie nie ma znaczenia. Chodzi o dopasowanie pierwszej lepszej pary, oddzielenie jej i szukanie kolejnej z liczb pozostałych.
3) Poszukiwana jest największa liczba rozwiązań
4) Na zestawie kilkunastu liczb chodzi o to aby wynik był tym "mniejszym" a dodać powstałe sumy "pełne", że tak sie wyrażę, można już manualnie aby nie komplikować pracy.
Jeśli tak to można bardzo przyspieszyć znajdowanie wyników, choć wszystko zależy od składników na wejściu. Ja zrobiłbym to tak:
1. posortować liczby na stosie: na górze małe, na dole duże
2. dodawać do siebie i sprawdzać po kolei mod 1000 sumy dwuskładnikowe, dalej trzy składnikowe itd. aż do sumy wszystkich elementów pozostałych na stosie
3. po każdym pozytywnym sprawdzeniu suma mod 1000 = 0 zdejmujemy składniki sumy ze stosu
Wystarczy modyfikacja kodu stasio, bo metoda jest bardzo podobna, tylko dochodzi trochę sprawdzania w locie i zdejmowanie ze stosu.
Aby przyspieszyć możemy to przenieść na C++, obliczenia zrównoleglić na dowolną ilość wątków (nie większą niż ilość rdzeni logicznych w procku), wykorzystać nVidia CUDA i Ati Stream :D
lekterus
07-08-2010, 16:48
http://pl.wikipedia.org/wiki/Optymalizacja_oprogramowania_%28informatyka%29
[/CODE]
i ?? Nadal nie rozumiem co wniosl ten link do tego co napisalem. Idz na wyzsza uczelnie i powiedz inzynierowi ze cos jest bardziej optymalne. Chetnie uslyszalbym co odpowie :D
i ?? Nadal nie rozumiem co wniosl ten link do tego co napisalem. Idz na wyzsza uczelnie i powiedz inzynierowi ze cos jest bardziej optymalne. Chetnie uslyszalbym co odpowie :D
Sam "zbitek" tych dwóch słów jest co prawda tautologią, ale wiadomo o co biega. Dla mnie (w tematyce tego wątku) to oznacza mniejszą złożoność obliczeniową, czyli takie przekształcanie pierwotnego algorytmu aby określone zadanie wykonywał szybciej przy wykorzystaniu co najwyżej tej samej ilości pamięci.
Dobrym do tego przykładem jest algorytm sortowania: bąbelkowe, przez wstawianie, przez scalanie, przez kopcowanie, quicksort. Najbardziej optymalnym z nich jest na ogół quicksort.
lekterus
07-08-2010, 19:22
Sam "zbitek" tych dwóch słów jest co prawda tautologią, ale wiadomo o co biega. Dla mnie (w tematyce tego wątku) to oznacza mniejszą złożoność obliczeniową, czyli takie przekształcanie pierwotnego algorytmu aby określone zadanie wykonywał szybciej przy wykorzystaniu co najwyżej tej samej ilości pamięci.
Dobrym do tego przykładem jest algorytm sortowania: bąbelkowe, przez wstawianie, przez scalanie, przez kopcowanie, quicksort. Najbardziej optymalnym z nich jest na ogół quicksort.
Czyli jedyni slowy ( a moze i nawet JEDNYM SLOWEM ) optymalnym. Stwierdzenie "najbardziej optymalne" dziala na mnie jak plachta na byka...ot takie zboczenie :)
Pozdrawiam
http://pl.wikipedia.org/wiki/Optymalizacja_oprogramowania_%28informatyka%29
co do programu stasio: co robi ta linijka i w jaki sposób?
$binstring = str_pad(decbin($a), $cnt, '0', STR_PAD_LEFT);
1. Zamienia zmienną $a na postać binarną (funkcja decbin)
2. Uzupełnia ją z lewej strony zerami do długości ciągu $cnt (funkcja str_pad)
Dla $cnt = 4 i $a = 2 wynikiem będzie: 0010
Pozdrawiam, Stasio.
Dzięki za odpowiedź i za zobrazownie działania:)
Miałem się zapytać po co to robi ale teraz już wiem:) bardzo sprytne i szybkie generowanie kombinacji:)
W twoim algorytmie wyrzuciłbym funkcję pow() przed while bo chyba przy każdym obiegu to liczy, a zmienna $cnt jest niezmienna;)
Powered by vBulletin® Version 4.2.5 Copyright © 2026 vBulletin Solutions, Inc. All rights reserved.