[es] - Mozgalica-kombinacija brojeva

Blue82
dipl. ecc.

Član broj: 165981
Poruke: 838
*.static.isp.telekom.rs.

+322 Profil

^{24.06.2010. u 11:31 - pre 168 meseci}

Kako poceti... Za one koji se razumeju u racunovodstvo, radi se o usaglašavanju kartica tj trazenju racuna koji nisu upareni.
Potrebno je upariti racune iz 2 kolone, kolone duguje i kolone potrazuje. Vizuelno to izgleda ovako:

Duguje...Potrazuje
10..........10
12..........8
15..........4
6...........8
11..........9
1............2
Nisam lepo predstavilo jer elite ne podrzava razmak da bih napravio kolone ali znaci imamo kolonu duguje i kolonu potrazuje. Cilj je pronaci sve kombinacije brojeva koje se sabiranjem mogu dobiti u koloni duguje i u koloni potrazuje te da pronadjemo brojeve koji nisu upareni.

U konkretnom primeru uparicemo brojeve:
10 iz kolone duguje sa 10 iz kolone potrazuje,
12 iz kolone duguje i (8+4=12) iz kolone potrazuje
(11+6=17) iz kolone duguje i (9+8=17) iz kolone potrazuje

I ostace mi neupareni brojevi 15,1 u koloni duguje i 2 u koloni potrazuje. Jednom sabran broj ne moze se više puta koristiti za sledece sabiranje(osim ako u istoj koloni nemamo više brojeva sa istom vrednosti).

pada li na pamet nekome zanimljiva funkcija ili petlja?

Odgovor na temu

Justice4All
programer
Srbija

Član broj: 263263
Poruke: 16
*.dynamic.isp.telekom.rs.

Profil

Re: Mozgalica-kombinacija brojeva

^{28.06.2010. u 23:18 - pre 168 meseci}

Baš si me bacio na razmišljanje... Ja se ovim problemom smaram već... pa, preko 18 godina... Problem je što ne znaš unapred koliko cifara sa koliko će se na kraju upariti pa broj kombincija deluje beskonačan. Npr, i ovo je moguća situacija:
10.....10
20.....1
0 .....1
0......1
itd... 20 jedinica....
A ista kombinacija može se desiti i s desna na levo....
Problem je u neurednom plaćanju računa i niko se zbog toga ne buni, bitno je da se nešto plati, a "sitnice" kao što su poziv na broj i TAČNA uplata po računu.. o tome nek se pobrinu programeri ( jedini ispravan sistem ima Telekom koji uplatu bez tačnog poziva na broj ne konstatuje!!!! - koliko su mi samo puta isekli tel zbog toga što sam platio noviji račun, čak i veći od onog prethodnog, jer je prethodni ostao nezatvoren). Dodatnu komplikaciju stvaraju poslovne banke od kojih neke zaokružuju iznose na ceo dinar a neke rade sa decimalama, tako da naš budući algoritam mora da sadrži i dozvoljenu grešku, s obzirom da se 2.324,30 i 2.324,00 zatvaraju iako će finansijska kartica imati dugovni saldo.

Nego da se vratim na (mogući) algoritam... Jedino što mi u ovom trenutku pada na pamet je najgrublja moguća sila: Uzmeš prvi broj sa leve strane pa probaš da nađeš isti takav sa desne (jedan prolaz-nadaš se da je bar nešto platio kako treba), onda probaš da nađeš dva takva broja, pa tri, sve dok ne istrošiš brojeve sa desne strane. (Ovo možda zvuči kao nešto što će se već posle par koraka multiplikovati na milijarde prolaza ali pretpostavljam da kombinacija nema baš previše-možda po par desetina sa obe strane a svaka kombinacija koja se zatvori automatski smanjuje broj učesnika igre). Isto to treba uraditi i s desna na levo, jer je moguće da kupac jednom uplatom reguliše više računa.

Tek posle toga, preći na kombinacije dva, tri... broja sa leve strane (i to isto s desna na levo). U praksi je redak (mada ne i nemoguć slučaj da se baš totalno haotično vrše uplate. Obično naprave račun pa ga plate iz dva-tri-..-n puta. Retko će se desiti situacija tipa:
100 ... 20
200 ... 310
100 ... 40
200 ... 300 tj. totalni haos - da čovek malo duguje pa malo uđe u preplatu, mada nije nemoguće a ni zabranjeno).

Ovo su samo razmišljanja iz prve ruke (mada o tome razmišljam već gore navedeni niz godina...) Probaću narednih dana da napravim nešto ili da izmozgam štogod pametnije, pa se čujemo.

Odgovor na temu

Nevena79
???

Član broj: 202308
Poruke: 335
*.adsl-a-1.sezampro.yu.

Sajt: www.tablic-klub.com

+1 Profil

Re: Mozgalica-kombinacija brojeva

^{29.06.2010. u 05:24 - pre 168 meseci}

Citat:

U praksi je redak (mada ne i nemoguć slučaj da se baš totalno haotično vrše uplate

hehe prijatelju, trenutno drzim karticu kod koje se jedan racun dobija sabiranjem 15 placanja :D
Jbg, iznosi su milionski pa se cepka. I to onda postaje nocna mora. A kada se dodje do usaglasenja kartica gleda se ne retko 4 godine u nazad sto je oko 10 listova a4 cistih promena. Zgodno za zabaviti se par dana :)

Odgovor na temu

Blue82
dipl. ecc.

Član broj: 165981
Poruke: 838
*.static.isp.telekom.rs.

+322 Profil

Re: Mozgalica-kombinacija brojeva

^{29.06.2010. u 17:13 - pre 168 meseci}

Ista situacija i kod mene. U sustini to je nista drugo nego kombinatorika 2 niza. Deluje prosto ali... :D

Odgovor na temu

Neznalica_sa_ugla
split

Član broj: 83282
Poruke: 390
*.st.cable.xnet.hr.

Profil

Re: Mozgalica-kombinacija brojeva

^{29.07.2010. u 23:04 - pre 167 meseci}

Evo malo kasno ,ali kako se i ja bavim sličnim problemnima , ja sam to ovako rješio ::

Duguje...Potrazuje // saldo
10..........10 10-10 0
12..........8 0+ 8-12 -4 još toliko platiti i svi prethodni računi zatvoreni
15..........4 -4+4- 15 -15 još toliko platiti i svi prethodni računi zatvoreni
6...........8 -15+8-6 -13 još toliko platiti i svi prethodni računi zatvoreni
11..........9 -13+9-11 -15 još toliko platiti i svi prethodni računi zatvoreni
1............2 -15+2-1 - 14 još toliko platiti i svi prethodni računi zatvoreni
Možda nije genijalno ,ali jedino moguće uparivanjem računa koji znadu biti i godinam neplaćeni , ... nemoguća misija , e da na kraju poslovne godine , se prenosi saldo i nastavlja poslovna blamaža

Odgovor na temu

sallle
Sasa Ninkovic
GTECH
Beograd

Član broj: 146
Poruke: 480
*.psit.rs.

ICQ: 20785904

+4 Profil

Re: Mozgalica-kombinacija brojeva

^{11.08.2010. u 14:18 - pre 166 meseci}

eo jednog brut fors pomalo seljackog resenja na prvu loptu:

uzmemo dugovnu stranu, i napravimo sve podskupove dugovanja, i nadjemo vrednosti tih podskupova (vrednost je suma svih elemenata u skupu) - toga ima oko 2^n. Te vrednosti uzmemo i sortiramo i dobijemo uredjen niz - dugovni niz .

Zatim isto uradimo i za potraznu stranu i dobijemo i tu neki uredjen niz sa 2^m clanova - potrazni niz.

Zatim uzmemo maximalni element u potraznom nizu , i pregledamo da li ta vrednost postoji u dugovnom nizu. ako postoji uparili smo citavo potrazivanje. Ako nismo nasli, uzimamo sledeci elemenat iz potraznog niza, i trazimo tu vrednost u dugovnom nizu. itd itd...

primer bi izgledao:

dugovanja: 1,2,4
potrazivanja: 3,1,1

dugovni podskupovi( {1,2,4},{2,4},{1,4},{1,2},{1},{2},{4}). dugovni niz vrednosti: 1,2,3,4,5,6,7
potrazni podskupovi({1,1,3},{1,3},{1,3},{1,1},{1},{1},{3}. potrazni niz vrednosti : 1,1,2,3,4,4,5

uzmemo 5 iz potraznog , i nalazimo tu vrednost u dugovnom:
potrazni elementi: 1,1,3
dugovni elementi: 1,4
(da nismo nasli 5 u dugovnom nizu, probali bi sa 4kom, ... itd).

Svakako da ovo moze da se optimizuje, nadje neki brzi algoritam. al danasnje masine ce lagano da izadju na kraj sa ovim ako je u pitanju 10tak elemenata.

za 20tak i vise, treba smisliti bolji algoritam :)

Odgovor na temu

sallle
Sasa Ninkovic
GTECH
Beograd

Član broj: 146
Poruke: 480
*.psit.rs.

ICQ: 20785904

+4 Profil

Re: Mozgalica-kombinacija brojeva

^{18.08.2010. u 10:36 - pre 166 meseci}

Za veci broj faktura, moze da se koristi princip koji se koristi za knapsack 0-1 problem (problem glasi otprilike, imamo torbu ogranicene zapremine, staviti sto vise stvari u tu torbu, tako da njihova vrednost bude maximalna, za svaku stvar imamo zadatu zapreminu i vrednost). Prilikom resavanja problema generise se matrica velicine [n,maxKapacitet] , n-broj elemenata, maxKapacitet - maximala zapremina/suma faktura.

za fakture bi izgenerisali dve ovakve matrice, jednu za dugovnu stranu, jednu za potraznu. i onda pretrazimo matrice i nadjemo najveci elemenat koji se poklapa...
slozenost algoritma bi bila O(N x maxSumaFaktura).

Odgovor na temu

Boris B.
Ljubljana

Član broj: 213615
Poruke: 286
95.176.144.*

+14 Profil

Re: Mozgalica-kombinacija brojeva

^{19.08.2010. u 23:04 - pre 166 meseci}

Jel zabranjeno u knjigovodstvu razduzivati sva zaduzenja hronoloski? Npr. svaka uplata pokriva najstariji neizmireni racun (ili racune), ako nije naveden poziv na broj? Znaci kao prazne kante koje se redom pune vodom, svaki put se napuni cela kanta do kraja i visak se sipa u sledecu.

Ako se ne radi tako, sta onda u slucaju 3 racuna po 200 din i jedna uplata od 200 din, koji racun razduziti?

if it walks like a duck and quacks like a duck, it could be a dragon doing a duck
impersonation.

Odgovor na temu