» »

Šah [Pacsal]

Šah [Pacsal]

Wh!tE ::

Jaz imam tukaj en problemček ker ne znam resit te naloga seveda ;) . Ja, naloga je sledeca....Imaš šahovnico 8x8 polj in na to šahovnico postaviš 8 kraljic tako da pokrijejo celo šahovnico. In sedaj vprašanje je: na koliko možnih (različnih seveda) načinov lahko postaviš te kraljice (8) na šahovnico tako, da pokriješ celo šahovnico.Ve kdo postopek kako to zračunaš? Upam da nism kompliciru z vprašanjem. :)
Hvala za vse odgovore :)
Me, the vanquisher

Thomas ::

for (x0=0;x0<8;x0++)
continue if queens attack each other
for x1
continue if queens attack each other
for x2
continue if queens attack each other
for x3

....

writeln x0,x1,x2 ...
.....
Man muss immer generalisieren - Carl Jacobi

Zgodovina sprememb…

  • spremenil: Thomas ()

Wh!tE ::

Tega jst ne razumem cisto dobro lahko pojasnis prosim. 8-)
Me, the vanquisher

Thomas ::

Seveda.

Prvo kraljico sprehajaš po vseh osmih A poljih v zunanji for zanki. Pa po osmih v B zanki v notranji zanki ... itd. 8 zank.

Med dvema zankama pogledaš, če se kakšni dve kraljici tepeta. Če se, greš na naslednje polje s to kraljico, ostale prej (v zunanjejših zankah) pustiš pri miru, ostale kasneje (v notranjejših zankah) pa poženeš znova. No, to ti naredi že struktura for zanke.

Po notranji for zanki izpisuješ rezultate.

Razumeš kej bolje?
Man muss immer generalisieren - Carl Jacobi

Wh!tE ::

Zdejle sm uzeu šah u roke pa se mal igram....Osimh kraljic na polju 8x8 sploh ne mores postavit tako da se nebi napadale?! Ali pač? 8-O Problem je ker lahko ze z 7mimi kraljicami pokrijes celo polje ane. Ali pa cemas kraljice vse v vrstici 1 je tud cela šahovnica pokrita.... :\
Me, the vanquisher

zigi ::

problem je rešljiv, na kak način se pa reši ti bo pa algoritem pokazal

AndrejS ::

Problem je rešljiv, celo na več načinov. Je pa res da ti bo dolgo računal program.

Thomas ::

Sem hotu povedat po slovensko.

Ampak FUCKIN GOOGLE IT!
Man muss immer generalisieren - Carl Jacobi

Wh!tE ::

Se opravičujem, niem dobro zastopil naloge...Očitno je vsem znana razen meni :) Thx anyway :)
Me, the vanquisher

Spasky77 ::

A4-B6-C8-D2-E7-F1-G3-H5 ena izmed več kot sto možnih varijant.

grain ::

Thomas ::


$DIMENSIONS X[2000] Y[2000]
$DECLAREINT x0 x1 x2 x3 x4 x5 x6 x7 y0 y1 y2 y3 y4 y5 y6 y7 zero upper dx dy i ok
$RETVAR X[] Y[]



upper=8;
upper--;
zero=0;
x0=0;x1=1;x2=2;x3=3;x4=4;x5=5;x6=6;x7=7;

for (y0=zero;y0&lt;=upper;y0++) {
 for (y1=zero;y1&lt;=upper;y1++) {
  dx=x1-x0;dx=abs(dx);dy=y1-y0;dy=abs(dy);
  ok=1;
  if (dx==zero) {ok=0;}
  if (dy==zero) {ok=0;}
  if (dx==dy) {ok=0;}
  if (ok!=zero) {
   for (y2=zero;y2&lt;=upper;y2++) {
    dx=x2-x0;dx=abs(dx);dy=y2-y0;dy=abs(dy);
    ok=1;
    if (dx==zero) {ok=0;}
    if (dy==zero) {ok=0;}
    if (dx==dy) {ok=0;}
    if (ok!=zero) {
     dx=x2-x1;dx=abs(dx);dy=y2-y1;dy=abs(dy);
     ok=1;
     if (dx==zero) {ok=0;}
     if (dy==zero) {ok=0;}
     if (dx==dy) {ok=0;}
     if (ok!=zero) {
      for (y3=zero;y3&lt;=upper;y3++) {
       dx=x3-x0;dx=abs(dx);dy=y3-y0;dy=abs(dy);
       ok=1;
       if (dx==zero) {ok=0;}
       if (dy==zero) {ok=0;}
       if (dx==dy) {ok=0;}
       if (ok!=zero) {
        dx=x3-x1;dx=abs(dx);dy=y3-y1;dy=abs(dy);
        ok=1;
        if (dx==zero) {ok=0;}
        if (dy==zero) {ok=0;}
        if (dx==dy) {ok=0;}
        if (ok!=zero) {
         dx=x3-x2;dx=abs(dx);dy=y3-y2;dy=abs(dy);
         ok=1;
         if (dx==zero) {ok=0;}
         if (dy==zero) {ok=0;}
         if (dx==dy) {ok=0;}
         if (ok!=zero) {
          for (y4=zero;y4&lt;=upper;y4++) {
           dx=x4-x0;dx=abs(dx);dy=y4-y0;dy=abs(dy);
           ok=1;
           if (dx==zero) {ok=0;}
           if (dy==zero) {ok=0;}
           if (dx==dy) {ok=0;}
           if (ok!=zero) {
            dx=x4-x1;dx=abs(dx);dy=y4-y1;dy=abs(dy);
            ok=1;
            if (dx==zero) {ok=0;}
            if (dy==zero) {ok=0;}
            if (dx==dy) {ok=0;}
            if (ok!=zero) {
             dx=x4-x2;dx=abs(dx);dy=y4-y2;dy=abs(dy);
             ok=1;
             if (dx==zero) {ok=0;}
             if (dy==zero) {ok=0;}
             if (dx==dy) {ok=0;}
             if (ok!=zero) {
              dx=x4-x3;dx=abs(dx);dy=y4-y3;dy=abs(dy);
              ok=1;
              if (dx==zero) {ok=0;}
              if (dy==zero) {ok=0;}
              if (dx==dy) {ok=0;}
              if (ok!=zero) {
               for (y5=zero;y5&lt;=upper;y5++) {
                dx=x5-x0;dx=abs(dx);dy=y5-y0;dy=abs(dy);
                ok=1;
                if (dx==zero) {ok=0;}
                if (dy==zero) {ok=0;}
                if (dx==dy) {ok=0;}
                if (ok!=zero) {
                 dx=x5-x1;dx=abs(dx);dy=y5-y1;dy=abs(dy);
                 ok=1;
                 if (dx==zero) {ok=0;}
                 if (dy==zero) {ok=0;}
                 if (dx==dy) {ok=0;}
                 if (ok!=zero) {
                  dx=x5-x2;dx=abs(dx);dy=y5-y2;dy=abs(dy);
                  ok=1;
                  if (dx==zero) {ok=0;}
                  if (dy==zero) {ok=0;}
                  if (dx==dy) {ok=0;}
                  if (ok!=zero) {
                   dx=x5-x3;dx=abs(dx);dy=y5-y3;dy=abs(dy);
                   ok=1;
                   if (dx==zero) {ok=0;}
                   if (dy==zero) {ok=0;}
                   if (dx==dy) {ok=0;}
                   if (ok!=zero) {
                    dx=x5-x4;dx=abs(dx);dy=y5-y4;dy=abs(dy);
                    ok=1;
                    if (dx==zero) {ok=0;}
                    if (dy==zero) {ok=0;}
                    if (dx==dy) {ok=0;}
                    if (ok!=zero) {
                     for (y6=zero;y6&lt;=upper;y6++) {
                      dx=x6-x0;dx=abs(dx);dy=y6-y0;dy=abs(dy);
                      ok=1;
                      if (dx==zero) {ok=0;}
                      if (dy==zero) {ok=0;}
                      if (dx==dy) {ok=0;}
                      if (ok!=zero) {
                       dx=x6-x1;dx=abs(dx);dy=y6-y1;dy=abs(dy);
                       ok=1;
                       if (dx==zero) {ok=0;}
                       if (dy==zero) {ok=0;}
                       if (dx==dy) {ok=0;}
                       if (ok!=zero) {
                        dx=x6-x2;dx=abs(dx);dy=y6-y2;dy=abs(dy);
                        ok=1;
                        if (dx==zero) {ok=0;}
                        if (dy==zero) {ok=0;}
                        if (dx==dy) {ok=0;}
                        if (ok!=zero) {
                         dx=x6-x3;dx=abs(dx);dy=y6-y3;dy=abs(dy);
                         ok=1;
                         if (dx==zero) {ok=0;}
                         if (dy==zero) {ok=0;}
                         if (dx==dy) {ok=0;}
                         if (ok!=zero) {
                          dx=x6-x4;dx=abs(dx);dy=y6-y4;dy=abs(dy);
                          ok=1;
                          if (dx==zero) {ok=0;}
                          if (dy==zero) {ok=0;}
                          if (dx==dy) {ok=0;}
                          if (ok!=zero) {
                           dx=x6-x5;dx=abs(dx);dy=y6-y5;dy=abs(dy);
                           ok=1;
                           if (dx==zero) {ok=0;}
                           if (dy==zero) {ok=0;}
                           if (dx==dy) {ok=0;}
                           if (ok!=zero) {
                            for (y7=zero;y7&lt;=upper;y7++) {
                             dx=x7-x0;dx=abs(dx);dy=y7-y0;dy=abs(dy);
                             ok=1;
                             if (dx==zero) {ok=0;}
                             if (dy==zero) {ok=0;}
                             if (dx==dy) {ok=0;}
                             if (ok!=zero) {
                              dx=x7-x1;dx=abs(dx);dy=y7-y1;dy=abs(dy);
                              ok=1;
                              if (dx==zero) {ok=0;}
                              if (dy==zero) {ok=0;}
                              if (dx==dy) {ok=0;}
                              if (ok!=zero) {
                               dx=x7-x2;dx=abs(dx);dy=y7-y2;dy=abs(dy);
                               ok=1;
                               if (dx==zero) {ok=0;}
                               if (dy==zero) {ok=0;}
                               if (dx==dy) {ok=0;}
                               if (ok!=zero) {
                                dx=x7-x3;dx=abs(dx);dy=y7-y3;dy=abs(dy);
                                ok=1;
                                if (dx==zero) {ok=0;}
                                if (dy==zero) {ok=0;}
                                if (dx==dy) {ok=0;}
                                if (ok!=zero) {
                                 dx=x7-x4;dx=abs(dx);dy=y7-y4;dy=abs(dy);
                                 ok=1;
                                 if (dx==zero) {ok=0;}
                                 if (dy==zero) {ok=0;}
                                 if (dx==dy) {ok=0;}
                                 if (ok!=zero) {
                                  dx=x7-x5;dx=abs(dx);dy=y7-y5;dy=abs(dy);
                                  ok=1;
                                  if (dx==zero) {ok=0;}
                                  if (dy==zero) {ok=0;}
                                  if (dx==dy) {ok=0;}
                                  if (ok!=zero) {
                                   dx=x7-x6;dx=abs(dx);dy=y7-y6;dy=abs(dy);
                                   ok=1;
                                   if (dx==zero) {ok=0;}
                                   if (dy==zero) {ok=0;}
                                   if (dx==dy) {ok=0;}
                                   if (ok!=zero) {
                                    X[i]=x0;Y[i]=y0;i++;X[i]=x1;Y[i]=y1;i++;X[i]=x2;Y[i]=y2;i++;X[i]=x3;Y[i]=y3;i++;X[i]=x4;Y[i]=y4;i++;X[i]=x5;Y[i]=y5;i++;X[i]=x6;Y[i]=y6;i++;X[i]=x7;Y[i]=y7;i++;
                                   }
                                  }
                                 }
                                }
                               }
                              }
                             }
                            }
                           }
                          }
                         }
                        }
                       }
                      }
                     }
                    }
                   }
                  }
                 }
                }
               }
              }
             }
            }
           }
          }
         }
        }
       }
      }
     }
    }
   }
  }
 }
}

Man muss immer generalisieren - Carl Jacobi

Zgodovina sprememb…

  • spremenil: Thomas ()

Wh!tE ::

GJ.:) . Eni ste pač bolj razgledani programerji kakor sem jaz (Rekurzija je zakomplicirana) :\
Me, the vanquisher

G_SamoV ::

To ni rekurzija. To je iteracija.

fireice ::

To sploh ni tezko za katerokoli stevilo postavit na roke. Samo vsako 3 liho se mi nekaj zatakne.

NeOman ::

ker morm zadevo ju3 oddat pri racunalnistvu vam pastam zadevo se tuki :). program ne poisce vseh resitev, po logiki bi moral... je pa narejen z rekurzijo in jih najde 85 / 92 (ne cez 100), pa se komentiran je, da vam bo lazje. ga posplosim na problem n dam na n × n veliki plosci (n razlicen od 2,3 ;) ).

program dame;
{program resi problem 8 dam na sahovnici}
uses crt;
type t=array[1..8,1..8] of integer;
var deska: t;
    resitve: integer;
procedure pocisti(stolpec: integer);
{procedura celo sahovnico 'pocisti' in oznaci vsa polja z 0}
var i,j: integer;
begin
   for i:=1 to 8 do
      for j:=stolpec to 8 do
         deska[i,j]:=0;
end;
procedure izris(var deska:t);
{procedura nam izrise sahovnico, kjer je v tabeli vrednost 0}
{tam ni dame, z 1 pa oznacimo polozaj dame}
var i,j: integer;
begin
   inc(resitve); {povecamo stevec resitev}
   clrscr;
   textcolor(15); writeln('Stevilka resitve: ',resitve,'.');
   for i:=1 to 8 do {izrisemo sahovnico: x - prazna polja}
      begin
      writeln;
      for j:=1 to 8 do
         if deska[i,j]=1 then begin
                                   textcolor(10);
                                   write(' @ '); { @ - dame }
                                   textcolor(15);
                              end
                              else write(' x '); {ni dame}
      writeln;
      end;
      writeln;
      writeln('Karkoli za nadaljevanje / ESC za izhod.');
      if (readkey=#27) then halt; {moznost ustavitve programa}
      writeln;
end;
function skeniraj(vrsta,stolpec:integer):boolean;
var i,j: integer;
    ni_spor: boolean; {spremenljivka, ki nam bo povedala ali lahko postavimo damo ali je kaksna v napoto}
begin
   ni_spor:=true; {na zacetku se ni ni_sporov, nobena izmed dam si ni v napoto}
   for j:=1 to stolpec-1 do
      if deska[vrsta,j]=1 then ni_spor:=false; {obstaja dama v isti vrstici}
   i:=vrsta;
   j:=stolpec;
   while (i>0) and (j>0) and (ni_spor=true) do
      begin
      dec(i); {pomaknemo se v prejsnjo vrstico}
      dec(j); {pomaknemo se v prejsnji stolpec}
      if deska[i,j]=1 then ni_spor:=false; {preverimo se trenuti polozaj, ce je tam postavljena dama}
      end;
   i:=vrsta;
   j:=stolpec;
   while (i>0) and (j>0) and (ni_spor=true) do
      begin
      inc(i); {pomaknemo se v naslednjo vrstico}
      dec(j); {pomaknemo se v naslednji stolpec}
      if (deska[i,j]=1) then ni_spor:=false; {preverimo se trenuti polozaj, ce je tam postavljena dama}
      end;
   skeniraj:=ni_spor; {ce imamo prosto pot lahko postavimo damo, procedura dobi vrednost true drugace false}
end;
procedure start(var deska:t; vrsta,stolpec:integer);
begin
if (stolpec>8) then izris(deska) {izrisemo 1 resitev}
               else
               repeat {ponavljamo toliko casa, da pridemo skozi sahovnico}
                      begin
                      pocisti(stolpec); {pocistimo vse stolpce}
                      if skeniraj(vrsta,stolpec)=true then {preverimo sahovnico}
                      begin
                           deska[vrsta,stolpec]:=1; {postavimo damo, ker nam to skeniranje omogoca}
                           start(deska,1,stolpec+1); {postavimo se nizje na sahovnico}
                      end;
                      inc(vrsta); {ko koncamo se premaknemo v novo vrsto}
                      end;
               until (vrsta>8);
end;
begin
start(deska,1,1);
end.


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

[MAT] Diferenciabilnost funkcije

Oddelek: Šola
142465 (1699) Unilseptij
»

Programiranje problem android

Oddelek: Programiranje
51088 (853) g333kk
»

[C++] Kako optimizirati?

Oddelek: Programiranje
112026 (1738) Vesoljc
»

Grafika

Oddelek: Programiranje
201608 (960) aaaaa93
»

n kraljic

Oddelek: Programiranje
141413 (1251) Thomas

Več podobnih tem