TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Newbie
Ahoj lidi, nedávno sem se pustil do jednoho programu, který dost usnadní život jednomu mému známému a zjistil sem, že to nebude asi až tak lehké, jak se na první pohled může zdát.
Takže asi takhle. Mám tabulku 7x7 předvyplněnou čísly (Načtu ji do 2d pole a pro jistotu ještě uložím do texťáku, pro kontrolu správnosti zadání všech souřadnic toho pole)..
Fakt je ten, že v tabulce součet všech buněk v jakémkoli řádku dá sumu 50. Tak to je, s tim se nesmí hnout.
Úkolem programu by mělo být postupně přerovnávat čísla v jednotlivých řádcích (NESMÍ se přehazovat čísla mezi řádky navzájem) a prokombinovat tak uplně celou tabulku a výstup by měl být
1.) První tabulka, na kterou program přišel, kde bude i součet řádků i součet sloupců roven 50ti
2.) Počet všech možných tabulek, kde bude i součet řádků i součet sloupců roven 50ti
... Problém nastává už tady. Samozřejmě v jednotlivých řádcích vytváříme všechny skupiny permutací 7. třídy, kterých bude 7!, neboli 5040. Řádků máme 7. To znamená kombinatorické pravidlo součinu nám říká, že to celkem bude 5040 na 7 cyklů což je KURWA VELKÝ ČÍSLO.
Program sem vytvořil pomocí cyklů For, kdy se postupně prohazovali v 1. řádku první dvě buňky, pak druhá se třetí, třetí se čtvrtou, čtvrtá s pátou, pátá se šestou, šestá se sedmou a tohle celé ještě 840x (Tím se proházel kompletně celý řádek, přec 840x6= právě oných 5040 Permutačních skupin.)
Ok, ale potom se ve druhém řádků musí prohodit první dvě buňky a proházet se opět totálně celý řádek. Celých 5040 Permutací :-D ... A to nemluvim o dalších řádcích.
Vím že PC jsou dnes rychlé, ale problém bude spíš v paměti. Trvá to hrozně dlouho. Je to z hlediska života jednoho tvora takřka nespočítatelný..
A má otázka zní, měl by někdo alternativu, která by PODSTATNĚ urychlyla výpočet této tabulky a dokonce i přišla na počet všech možných tabulek, které by odpovídaly výše uvedeným kritériím? :-)
Díky moc!
Fórum › Delphi
Tabulka 7x7... Někdo nápad?
Nahlásit jako SPAM
IP: 213.129.130.–
Stálý členEDIT - reseni taky nemam :D
nj, jasne, to sem prehlid....
God of flame2.) Počet všech možných tabulek, kde bude i součet řádků i součet sloupců roven 50ti
todle ti primo rika ze musis vsechny ty permutace projit.. jinak to nejsi schopen nikdy zjistit
ideal by bylo zrcadleni (coz by predpokladalo v kazdem radku stejne hodnoty)
prvni reseni by bylo asi nejlepsi resit nejakym trochu inteligentnim algoritmem .. napriklad zjistit o kolik se jednotlive sloupce lisi od 50 a vybrat hodnoty, ktere co nejvice priblizi prave k te padesatce... akorat hrozi, ze to nemusi mit reseni.. - mohlo by se to zacyklit bez nejakeho ukladani aspon hodnot sloupcu a hledani zda uz si na takove hodnote nebyl
To KIIV : Jj. Přesně tak. Taky sem to zkoušel, i třeba ručně v excelu. Dole sem si nastavil ty sumy a jel jsem ... vzal jsem dva extrémy, třeba 36 a 68 .. spočítal jejich rozdíl a snažil se přehodit na řádcích ty hodnoty, které by ten rozdíl co nejpřesněji smazaly .. Bohužel, zacyklil sem se :-)
To KIIV : Nerozumim? Ta konkrétní tabulka má 100% řešení .. a těch bude dost, ale prostě sem se dostal do nekonečný smyčky. Chce to ten samej algoritmus, ale napsat jinak .. A šetřit tim hodně paměť na proměný a vůbec .. zjednodušit výrazně celej kód
GuruZkusil bych na to jít takto:
- pro každé číslo z prvního řádku najít všechny kombinace, které pro něj dají ve sloupci součet 50
- tyto kombinace si ukládat, protože se jedná o jediné možné, které povedou pro dané číslo (ať je v jakékoliv pozici) k možnému výsledku
- tím ti řádně (doufám :)) prořídne stavový prostor
- nyní kombinovat tyto možnosti tak, aby každé číslo v řádku bylo použito jen jednou
To KIIV : Čísla tu jsou .. někde výš sem házel obrázek.. Každopádně mohl, ale takhle bych nenašel nikdy všechny, to je jedna věc .. a druhá je ta, že on si je poskládá a už s nimi nehýbe .. dojede na konec k poslednímu sloupci a ten mu nevyjde 50.. :-)
To liborb : Supr nápad. Každopádně co s řádkama, kde se vyskytuje jedno a to samé číslo třeba 2x, nebo 3x? jak to ošetřit?
To na věci skoro nic nemění, jen to mírně zesložití testování :). Mě by spíš zajímalo, kolik je to pro jednotlivá čísla z prvního řádku možností a podle toho bych se zařídil dále. A jen tak mimochodem asi víš, že když si našel jedno řešení, tak další se nabízí přesouvání celých sloupců ...
To DJ_Rabbit : pokud dojedes na konec a posledni sloupec ti nezbyde 50 tak tezko muzes najit reseni ..
jinak rychle overeni by mohlo byt ze soucet vsech hodnot vyjde 350
tak sem zkousel vsechny kombinace radku a vyslo mi 20264 kombinaci (i s duplicitami) sloupcu, ktere daji soucet 50...
ted uz to jen vhodne zkombinovat tak, aby se v reseni nepouzilo stejne cislo vicekrat...
no bude to tak jak tak chtit nejakou vychytavku..
To KIIV : S tím součtem 350 to nevidim dobře. Protože 350 se dá mezi 7 partiček rozložit i jinak než 7*50.
Resp. 40+50+50+50+50+50+60= taky 350.
Btw vyšlo mi to stejně ...
Jinak každopádně to půjde ořezat o jeden řádek, tzn udělat z toho matici 7x6.
20k možností je mnohem lepší jak 7! na 7 možností :). Škoda, že jste nenapsali, kolik je kombinací pro každé číslo z prvního řádku. Teď bych postupoval tak, že bych generoval jednotlivé kombinace a testoval:
- jestli součet na řádcích je 50 (hrubé rozlišení)
- jestli jsou použity právě čísla dané na řádek (ověření)
To liborb : Ale notak ... 20k možností má jenom to, když zjistim možnej první řádek .. To vůbec neberu v úvahu ostatní .. To se větví, že jo .. Jinak udělal jsem program pro tabulku 4x4, kterej funguje tak jak má, takže se jenom snažit to napodobit a vepsat do toho .. Dělá se to pomocí 3 polí. Jedno, do toho se načtou hodnoty z klávesnice, to je základ. Druhý, to je jeho kopie, akorád že v tý se to přehazuje .... A třetí, to je pomocný, do kterýho se zapisujou jenom jedničky, nebo nuly, aby věděl, že tohle číslo z prvního pole už je obsazený a že má jít v cyklu zleva doprava dál, dokud nenarazí na to, že v pomocnym poli nic není ... to zapíše a jede dál.. :-)
Dá mi to pár dnů a je to na světě. Hodim to potom sem, kdyby to někohozajímalo
20tisic moznosti je pocet ruznejch kombinaci jednoho sloupce ktery da soucet 50..
pokud by si to prochazel vsechno v 7mi urovnich tak to da mnohem horsi vysledek.. ale to neni potreba .. do nizsich urovni muzes az pozdeji ... takze se nebudou prochazet vsechny kombinace
optimalizace by byla taky pouzit bitovou mapu pro jednotlive radky a ktere pozice sloupcu uz tam sou .. (pro rychle srovnani jestli to ma cenu pouzit nebo ne) a tak dale (vse se vejde do jednoho 64b cisla) nebo dvou 32 (potrebujes 49bitu)... pokud narazis na nove pridavany ktery je uz uvnitr tak uz vyrazujes moznost protoze stejny cislo 2x v radku mit nemuzes
Tak jsem si to zkusil, abych viděl, jak mě tu vodíte za nos :). Takže to číslo 20264 existuje, ale je to součet kombinací pro jednotlivá první čísla, tj. to číslo nemá žádnou informační hodnotu. Důležité je spíše to, že pro 7 v prvním řádku lze v ostatních řádcích vytvořit 3113 kombinací, aby součet ve sloupci byl 50. Je to sice velké číslo, ale proti 6 na 7 (279936) je to zlepšení :).
Pokračování toho je zkoušení jen těchto možný kombinací, kterých celkem bude (jestli se nepletu) 3113 * 2870 * ... . Samozřejmě, některé (většina) jsou nesmyslné a ty je potřeba vyřadit (viz výše).
A když najdeš těch "pár", pro které bude všude součet 50, tak výsledek stačí vynásobit 7! a máš konečné číslo.
Ale je pravda, že jsem mohl něco přehlédnout :)
Třeba na to taky dojde :), ale zatím spíše jen to kibicování ;).
Kdybych to programoval, tak bych si kombinace pro jednotlivá čísla v prvním řádku uložit do polí (tj. 6 polí o velikosti počet kombinací x 7). Následně bych je zkoušel ... otázkou je, co by bylo nejrychlejší, ale možná "hledat" dle zatím vybraných sloupců ty, které jsou možné (jedno číslo není použité víckrát). Tím by se asi nejrychleji vyřadili nesmyslné kombinace a podmínka na součet v řádku 50 ti vyjde automaticky.
To liborb : prave proto sem zminovat tu bitovou mapu...
mit treba:
1000000 0001000 0010000 1000000 0000010 0000001 0000001
a v druhem sloupci bude
0100000 0010000 0100000 0000010 0100000 0000001 0000010
pak logicky soucin hodi:
0000000 0000000 0000000 0000000 0000000 0000001 0000000 - a rekne ze to ma vyradit...
kdyby se neprekryvaly tak logicky soucet a kontrolovat s tim ... usetrila by se spousta zbytechnejch "podcyklu" - takhle se vsechny uz zpracovany a spravny sloupce promitnou rovnou do srovnavane hodnoty
takze jedno vlakno na Core 2 Duo notebookovym procesoru - od kazdy variace prvniho sloupce jedno reseni za cca 34s
(akorat to nevypisuju nijak srozumitelne.. jen ty jednotlivy bitovy masky )
bez vypisovani 19s
akorat sem tam neresil pocet variaci.. je to jen pro tento pripad - tj 20264
najdu stejny pocet reseni, pokazde s jinym prvnim sloupcem
pokud sem prochazel vsechny tak kolem 2 milionu sem to stopl .. kombinovalo mozna nekde u poslednich sloupcu
nicmene prvni reseni to zvladne velice rychle
a jeste "kod":
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 7
#define ULLI unsigned long long int
#define SLOUPCU 20264
int reseni = 0;
unsigned int tstart;
int recurse( ULLI * x, ULLI * funkcni, char depth, ULLI logic_sum) {
int i ;
if ( depth == 7 ) {
reseni ++;
printf("Reseni .. %d \n", reseni);
for ( i=0; i<SIZE; i++ ) {
printf(" %016I64X\n", funkcni[i]);
}
return 1;
}
for ( i=0; i < SLOUPCU ; i++ ) {
if ( (logic_sum & x[i]) == 0 ) {
funkcni[depth] = x[i];
int r = recurse( x, funkcni, depth+1, logic_sum | x[i] );
if ( (depth>0) && (r!=0) ) {
return 1;
}
}
}
return 0;
}
int main(int argc, char *argv[])
{
unsigned char all[] = {
7, 5, 0, 16, 15, 2, 5,
5, 3, 19, 9, 3, 8, 3,
9, 1, 12, 12, 1, 10, 5,
3, 3, 21, 6, 4, 6, 7,
2, 14, 11, 3, 11, 1, 8,
7, 13, 0, 2, 8, 16, 4,
4, 12, 1, 0, 26, 5, 2,
};
int i, tmp, sum = 0, cnt=0;
unsigned int a = 0;
unsigned char xx[7] = {0}, l;
ULLI * speed = malloc(sizeof(ULLI) * SLOUPCU);
ULLI * snapshot = malloc( sizeof(ULLI) * SIZE );
for ( a=0; a<823543; a++ ) {
ULLI tmpL = 0;
sum = 0;
i = 0;
tmp = a;
for ( i=0 ; i < 7 ; i++ ) {
l = tmp % 7;
tmpL = (tmpL << 7) | (1 << l);
sum += all[i*7 + l];
xx[i] = all[i*7 + l];
tmp /= 7;
}
if (sum == 50) {
speed[cnt] = tmpL;
cnt++;
}
}
tstart = time(NULL);
recurse(speed, snapshot, 0, 0); // depth=0 mask=0
printf("posledni pocet reseni: %d za cca: %u\n",reseni, time(NULL) - tstart);
return 0;
}
Já to dělal pomocí tří polí. Jedno základní s hodnotama, druhý je jeho kopie, s tim se pracuje na základě hodnot prvního pole .. a třetí pomocný. Všechny maj rozměr 7x7. Do pomocnýho se na souřadnice čísel z prvního pole, který jsou ve druhym už použitý zapisuje vždy 1. Program pak hledá, jestli tam jednička je, pokud ano, zapíše hned další v řadě, pokud tam zas není jednička (Tím jsem vyloučil možné opakování se číslic a tedy chybné kombinování jednotlivých řádků. čili toto je dle mého názoru jediný, správný algoritmus pro nalezení všech skupin).
Ještě je tam jedna vychytávka a to ta, protože program jede takto
A B C D
A B D C
A C B D
A C D B
A D B C
A D C B
B A C D
B A D C
............
||||||||||
|||||||||| atd...
, že pokud jsou dvě zadní číslice stejné, tak je program neobrací. řeknete si, joo, tim se moc neušetří. Houbelec :-) Tabulka 4x4 má celkem 13 824 cyklů (Poslední řádek může stát, tím vylučuji dalších 23 možností na jednu správno [přeházení sloupců mezi sebou])
A jenom tim, že nepřehazuju zadní dvě číslice, pokud jsou stejné, ušetřil na mnou vymyšlené tabulce 4x4 2 208 cyklů :-) Což je hezký, že?
Stejně to bude fungovat i pro 7x7, ale bude to dost složitější. Pokud chcete porozumět, doporučuju odkrokovat program, abyste viděli pár prvních zápisů a bude vám to jasný hned. (+ nakreslit všechna 3 pole na papír a jet s nim)
Jo ještě kód.
program MalyRebus;
{$APPTYPE CONSOLE}
uses
SysUtils;
var
a,b,u,v,k,l: integer;{Hlavni proměnné pro cykly For}
x,y: integer; {Pomocné proměnné pro zápis správné tabulky do *.txt}
c,d,e: integer; {Vnitřní proměnné pro přehazování místeček v polích}
PocetPoli: Integer;
Zapisuj: Boolean;
{Pom: array[1..4] of integer;}
Pole,Pole_2,Pom: array[1..4,1..4] of integer;
vysledna: TextFile;
begin
AssignFile(vysledna,'vysledna.txt');
rewrite(vysledna);
Fillchar(Pole,SizeOf(Pole),0);
Fillchar(Pole_2,SizeOf(Pole_2),0);
Fillchar(Pom,SizeOf(Pom),0);
PocetPoli:=0;
Zapisuj:=True;
For a:=1 to 4 do
Begin
For b:=1 to 4 do
Begin
write('Zadej prvek se souradnici ',a,',',b,': ');
readln(Pole[a,b]);
end;
end; {Načítací a zaváděcí část}
Pole_2:=Pole;
{------------------------------------------------}
{Výpočtová a vypisovací část}
for a:=1 to 4 do
begin
Pole_2[1,1]:=Pole[a,1];
For b:=1 to 4 do
Begin
if a<>b then
begin
Pom[1,1]:=0;
Pom[2,1]:=0;
Pom[3,1]:=0;
Pom[4,1]:=0;
Pole_2[2,1]:=Pole[b,1];
Pom[b,1]:=1; Pom[a,1]:=1;
c:=1;
while Pom[c,1]=1 do c:=c+1;
Pole_2[3,1]:=Pole[c,1];
Pom[c,1]:=1;
d:=c;
while Pom[d,1]=1 do d:=d+1;
Pole_2[4,1]:=Pole[d,1];
if (Pole_2[1,1]+Pole_2[1,2]+Pole_2[1,3]+Pole_2[1,4]=10) and
(Pole_2[2,1]+Pole_2[2,2]+Pole_2[2,3]+Pole_2[2,4]=10) and
(Pole_2[3,1]+Pole_2[3,2]+Pole_2[3,3]+Pole_2[3,4]=10) and
(Pole_2[4,1]+Pole_2[4,2]+Pole_2[4,3]+Pole_2[4,4]=10) then
Begin
PocetPoli:=PocetPoli+1;
end;
if (PocetPoli>0) and (Zapisuj=True) then
Begin
For y:=1 to 4 do
Begin
For x:=1 to 4 do
Begin
write(vysledna,Pole_2[x,y]);
if Pole_2[x,y]<10 then
write(vysledna,' ')
else write(vysledna,' ');
end;
writeln(vysledna);
end;
Zapisuj:=False;
writeln(vysledna);
writeln(vysledna);
writeln(vysledna);
end;
if Pole_2[3,1]<>Pole_2[4,1] then {Pokud zadní dvě nejsou stejné, pak se prohazují a zjišťuje se znovu.}
Begin
e:=Pole_2[3,1]; Pole_2[3,1]:=Pole_2[4,1]; Pole_2[4,1]:=e;
if (Pole_2[1,1]+Pole_2[1,2]+Pole_2[1,3]+Pole_2[1,4]=10) and
(Pole_2[2,1]+Pole_2[2,2]+Pole_2[2,3]+Pole_2[2,4]=10) and
(Pole_2[3,1]+Pole_2[3,2]+Pole_2[3,3]+Pole_2[3,4]=10) and
(Pole_2[4,1]+Pole_2[4,2]+Pole_2[4,3]+Pole_2[4,4]=10) then
Begin
PocetPoli:=PocetPoli+1;
end;
if (PocetPoli>0) and (Zapisuj=True) then
Begin
For y:=1 to 4 do
Begin
For x:=1 to 4 do
Begin
write(vysledna,Pole_2[x,y]);
if Pole_2[x,y]<10 then
write(vysledna,' ')
else write(vysledna,' ');
end;
writeln(vysledna);
end;
Zapisuj:=False;
writeln(vysledna);
writeln(vysledna);
writeln(vysledna);
end;
end;
for u:=1 to 4 do
begin
Pole_2[1,2]:=Pole[u,2];
For v:=1 to 4 do
Begin
if u<>v then
begin
Pom[1,2]:=0;
Pom[2,2]:=0;
Pom[3,2]:=0;
Pom[4,2]:=0;
Pole_2[2,2]:=Pole[v,2];
Pom[v,2]:=1; Pom[u,2]:=1;
c:=1;
while Pom[c,2]=1 do c:=c+1;
Pole_2[3,2]:=Pole[c,2];
Pom[c,2]:=1;
d:=c;
while Pom[d,2]=1 do d:=d+1;
Pole_2[4,2]:=Pole[d,2];
if (Pole_2[1,1]+Pole_2[1,2]+Pole_2[1,3]+Pole_2[1,4]=10) and
(Pole_2[2,1]+Pole_2[2,2]+Pole_2[2,3]+Pole_2[2,4]=10) and
(Pole_2[3,1]+Pole_2[3,2]+Pole_2[3,3]+Pole_2[3,4]=10) and
(Pole_2[4,1]+Pole_2[4,2]+Pole_2[4,3]+Pole_2[4,4]=10) then
Begin
PocetPoli:=PocetPoli+1;
end;
if (PocetPoli>0) and (Zapisuj=True) then
Begin
For y:=1 to 4 do
Begin
For x:=1 to 4 do
Begin
write(vysledna,Pole_2[x,y]);
if Pole_2[x,y]<10 then
write(vysledna,' ')
else write(vysledna,' ');
end;
writeln(vysledna);
end;
Zapisuj:=False;
writeln(vysledna);
writeln(vysledna);
writeln(vysledna);
end;
end;
if Pole_2[3,2]<>Pole_2[4,2] then {Pokud zadní dvě nejsou stejné, pak se prohazují a zjišťuje se znovu.}
Begin
e:=Pole_2[3,2]; Pole_2[3,2]:=Pole_2[4,2]; Pole_2[4,2]:=e;
if (Pole_2[1,1]+Pole_2[1,2]+Pole_2[1,3]+Pole_2[1,4]=10) and
(Pole_2[2,1]+Pole_2[2,2]+Pole_2[2,3]+Pole_2[2,4]=10) and
(Pole_2[3,1]+Pole_2[3,2]+Pole_2[3,3]+Pole_2[3,4]=10) and
(Pole_2[4,1]+Pole_2[4,2]+Pole_2[4,3]+Pole_2[4,4]=10) then
Begin
PocetPoli:=PocetPoli+1;
end;
if (PocetPoli>0) and (Zapisuj=True) then
Begin
For y:=1 to 4 do
Begin
For x:=1 to 4 do
Begin
write(vysledna,Pole_2[x,y]);
if Pole_2[x,y]<10 then
write(vysledna,' ')
else write(vysledna,' ');
end;
writeln(vysledna);
end;
Zapisuj:=False;
writeln(vysledna);
writeln(vysledna);
writeln(vysledna);
end;
end;
for k:=1 to 4 do
begin
Pole_2[1,3]:=Pole[k,3];
For l:=1 to 4 do
Begin
if k<>l then
begin
Pom[1,3]:=0;
Pom[2,3]:=0;
Pom[3,3]:=0;
Pom[4,3]:=0;
Pole_2[2,3]:=Pole[l,3];
Pom[l,3]:=1; Pom[k,3]:=1;
c:=1;
while Pom[c,3]=1 do c:=c+1;
Pole_2[3,3]:=Pole[c,3];
Pom[c,3]:=1;
d:=c;
while Pom[d,3]=1 do d:=d+1;
Pole_2[4,3]:=Pole[d,3];
if (Pole_2[1,1]+Pole_2[1,2]+Pole_2[1,3]+Pole_2[1,4]=10) and
(Pole_2[2,1]+Pole_2[2,2]+Pole_2[2,3]+Pole_2[2,4]=10) and
(Pole_2[3,1]+Pole_2[3,2]+Pole_2[3,3]+Pole_2[3,4]=10) and
(Pole_2[4,1]+Pole_2[4,2]+Pole_2[4,3]+Pole_2[4,4]=10) then
Begin
PocetPoli:=PocetPoli+1;
end;
if (PocetPoli>0) and (Zapisuj=True) then
Begin
For y:=1 to 4 do
Begin
For x:=1 to 4 do
Begin
write(vysledna,Pole_2[x,y]);
if Pole_2[x,y]<10 then
write(vysledna,' ')
else write(vysledna,' ');
end;
writeln(vysledna);
end;
Zapisuj:=False;
writeln(vysledna);
writeln(vysledna);
writeln(vysledna);
end;
end;
if Pole_2[3,3]<>Pole_2[4,3] then {Pokud zadní dvě nejsou stejné, pak se prohazují a zjišťuje se znovu.}
Begin
e:=Pole_2[3,3]; Pole_2[3,3]:=Pole_2[4,3]; Pole_2[4,3]:=e;
if (Pole_2[1,1]+Pole_2[1,2]+Pole_2[1,3]+Pole_2[1,4]=10) and
(Pole_2[2,1]+Pole_2[2,2]+Pole_2[2,3]+Pole_2[2,4]=10) and
(Pole_2[3,1]+Pole_2[3,2]+Pole_2[3,3]+Pole_2[3,4]=10) and
(Pole_2[4,1]+Pole_2[4,2]+Pole_2[4,3]+Pole_2[4,4]=10) then
Begin
PocetPoli:=PocetPoli+1;
end;
if (PocetPoli>0) and (Zapisuj=True) then
Begin
For y:=1 to 4 do
Begin
For x:=1 to 4 do
Begin
write(vysledna,Pole_2[x,y]);
if Pole_2[x,y]<10 then
write(vysledna,' ')
else write(vysledna,' ');
end;
writeln(vysledna);
end;
Zapisuj:=False;
writeln(vysledna);
writeln(vysledna);
writeln(vysledna);
end;
end;
end;
end;
end;
end;
end;
end;
end;
closefile(vysledna);
writeln('Hotovo.');
writeln('Bylo nalezeno celkem: ',PocetPoli,' tabulek,prvni byla zapsana do souboru vysledna.txt');
writeln('Stisknutim ENTER ukoncite program...');
readln;
end.Tak jsem přidám ještě jedno řešení v C :). To KIIV: je tam použit tvůj nápad s bitovou maskou ;). Generuje to až neuvěřitelné množství možností, tak stejně jako KIIV ... snad jsem někde neudělal chybu :). Bez vypisování by to frčelo asi o něco rychleji, ale i tak si to nějaký čas vezme.
int nData[7][7] = {{7, 5, 0, 16, 15, 2, 5},
{5, 3, 19, 9, 3, 8, 3},
{9, 1, 12, 12, 1, 10, 5},
{3, 3, 21, 6, 4, 6, 7},
{2, 14, 11, 3, 11, 1, 8},
{7, 13, 0, 2, 8, 16, 4},
{4, 12, 1, 0, 26, 5, 2}};
int nTotal = 0;
int nCount[7] = {0, 0, 0, 0, 0, 0, 0};
unsigned long long** pnTab;
// spocteni moznosti pro jednotliva cisla z prvniho radku
for (int i = 0;i < 7;i++) {
for (int j = 0;j < 7;j++) {
for (int k = 0;k < 7;k++) {
for (int l = 0;l < 7;l++) {
for (int m = 0;m < 7;m++) {
for (int n = 0;n < 7;n++) {
for (int o = 0;o < 7;o++) {
int nSuma = nData[0][i] + nData[1][j] + nData[2][k] + nData[3][l] + nData[4][m] + nData[5][n] + nData[6][o];
if (nSuma == 50) {
nTotal++;
nCount[i]++;
}
}
}
}
}
}
}
}
pnTab = new unsigned long long*[7];
for (int i = 0;i < 7;i++) {
pnTab[i] = new unsigned long long[nCount[i]];
}
memset(&nCount, 0, sizeof(nCount));
// ulozeni moznych kombinaci v bitove podobe
for (int i = 0;i < 7;i++) {
for (int j = 0;j < 7;j++) {
for (int k = 0;k < 7;k++) {
for (int l = 0;l < 7;l++) {
for (int m = 0;m < 7;m++) {
for (int n = 0;n < 7;n++) {
for (int o = 0;o < 7;o++) {
int nSuma = nData[0][i] + nData[1][j] + nData[2][k] + nData[3][l] + nData[4][m] + nData[5][n] + nData[6][o];
if (nSuma == 50) {
unsigned long long nResult = ((unsigned long long)1 << j)
| ((unsigned long long)1 << (7 + k)) | ((unsigned long long)1 << (14 + l)) | ((unsigned long long)1 << (21 + m))
| ((unsigned long long)1 << (28 + n)) | ((unsigned long long)1 << (35 + o));
pnTab[i][nCount[i]] = nResult;
nCount[i]++;
}
}
}
}
}
}
}
}
// hledani vysledku
nTotal = 0;
for (int i = 0;i < nCount[0];i++) {
for (int j = 0;j < nCount[1];j++) {
// oriznuti jasne nesmyslnych kombinaci
if ((pnTab[0][i] & pnTab[1][j]) != 0) continue;
for (int k = 0;k < nCount[2];k++) {
if (((pnTab[0][i] | pnTab[1][j]) & pnTab[2][k]) != 0) continue;
for (int l = 0;l < nCount[3];l++) {
if (((pnTab[0][i] | pnTab[1][j] | pnTab[2][k]) & pnTab[3][l]) != 0) continue;
for (int m = 0;m < nCount[4];m++) {
if (((pnTab[0][i] | pnTab[1][j] | pnTab[2][k] | pnTab[3][l]) & pnTab[4][m]) != 0) continue;
for (int n = 0;n < nCount[5];n++) {
if (((pnTab[0][i] | pnTab[1][j] | pnTab[2][k] | pnTab[3][l] | pnTab[4][m]) & pnTab[5][n]) != 0)
continue;
for (int o = 0;o < nCount[6];o++) {
unsigned long long nResult = pnTab[0][i] | pnTab[1][j] | pnTab[2][k] | pnTab[3][l]
| pnTab[4][m] | pnTab[5][n] | pnTab[6][o];
if (nResult == 0x3FFFFFFFFFF) {
nResult = nResult;
nTotal++;
printf("Reseni cislo: %u (%d, %d, %d, %d, %d, %d, %d)\n", nTotal, i, j, k, l, m, n, o);
}
}
}
}
}
}
}
}
// uvoleni pameti
for (int i = 0;i < 7;i++) {
delete [] pnTab[i];
}
delete [] pnTab;
return 0;To liborb : skoda jen, ze pocitas celou logickou sumu takhle pokazdy znova :) mit jednu lokalni promennou v kazdym cyklu a hodit a1 = a0 | neco.. tak by to lehce zrychlilo .. hlavne na tech vetsich urovnich.. ale pokud vypisujes tak to nebude to nejpomalejsi
Tabulka má vždy minimálně jedno řešení ne-li víc,fyzicky ověřeno,čísla do jednotlivých řádků se doplňují
z jiných tabulek;co řádek to jedna tabulka ale obsah jednotlivých buněk v poli 7x7 se mění podle těchto tabulek
kde je součet zase 50.K prvnímu číslu prvního řádku se použijí ke kombinacím již jen řádky 2 až 7 pro vytvoření
sloupců se součtem 50.Tam je počet možností 117649.K druhému číslu prvního řádku se vybírají zase čísla
z řádků 2 až 7 ale bez těch které byly použity pro první výběr,tady zůstává ještě 46656 možností volby.K tomu
prvnímu výběru čísel my tam vychází několik set správných možností a ke každé je nutno hledat v druhém a dalším
hledání všechny matematické kombinace,ale bez použití již těch vybraných čísel.A tak dále.Pro třetí číslo prvního
řádku zbývá už jen 15625 možností,dále pro 4 č. prvního ř. je jen 4094 možností pro 5č. 1ř. je 729 možností a pro
6č. 1ř. zbylo jen 64 variant.Na 7č. nebo taky sloupek je jen jedna možnost.Může-li my někdo poradit byl bych rád.
cent.cent@centrum.cz
Zjistit počet nových příspěvků
Přidej příspěvek
Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku
×Vložení zdrojáku
×Vložení obrázku
×Vložení videa
Uživatelé prohlížející si toto vlákno
Podobná vlákna
Nápad na portál — založil Mickey
Nápad na šifrování — založil Matěj Andrle
Nápad na projekt — založil Martyn
Štvorce - nápad na engine? — založil miso3367
Napad na pekny projekt — založil fisher55
