Latin Square

[cucumber]

Ir dots masivs piem:

1,2,3

2,3,1

3,1,2

kas saucas ari Latin Square(kaut kada lidziba sudoku, tikai mazaks), shis kvadrats ir sakartos pec fisiem latin kvadrata likumiem, bet shis nav

1,2,3

1,3,2

3,1,2. Man jautajums pec kada algoritma to varetu vieglak pateikt ka shis kvadrats nav lantin kvadrats.

 

Neesmu parliecinats vai shis metodes stradas, bet tomer:

 

1. Metode

1.Lietotajs ievadijis kavadrats 4x4 elementus liels, talak matrica.

2.Uztaisu isto latin kvadratus uzzinu matricas determinantu.

3.Tad to salidzinu ar to ko ievadijis lietotajs un ja determinanti ir atshkirigi, secinu ka nav pareizs. determinats var but viens un tas pats skaitlis tikai ar plus var ar minis tapec abs(determinatsNoMatricas)

 

 

2.Metode

1.Panem pirmo masiva rindu apskatos vai tani skaitli neatkartojas

2.Ja neatkartojas nemu sho rindu ka etalonu

3.Salidzinu ar parejam rindam uz sakritibu

4. Ja nesakrit nemu nakamo rindu un daru 4

 

 

 

Varbut, ir kads labaks, effektivaks risinajums?

[Val]

summas katrai rindai un katrai kolonnai jābūt vienādām. bet vai tas der, nezinu.

Edited October 4, 2007 by Val

[cucumber]

1,2,3 =6

2,2,2 =6

3,2,1 =6

----------

6,6,6

 

Secinajums neder!

[andrisp]

Ja pareizi, tad:

http://paste.php.lv/6191/

 

$x mainīgais tur nejauši palika. :) Nav vajadzīgs viņš tur.

 

PS. cucumber, lūdzu, raksti tomēr nedaudz uzmanīgāk.

Edited October 4, 2007 by andrisp

[cucumber]

Ja tev ir realizacija,bet man vajaga metodi jeb algoritmu, lai to realizetu uz C++ izmantojot tikai iostream biblioteku.

 

ps, kam vajadzigs $x koda? Nu ja paspeji pielabot :)

Edited October 4, 2007 by cucumber

[andrisp]

Vot nu tas tev būs jāprasa kāda C++ forumā nevis te. Bet vispār tā realizācija ir tik vienkārša, ka domāju, ka iekš C++ tam visam vajadzētu arī būt viegli. Sintaksīti tikai pielabo attiecīgi. Nujā - array_unique analogs varētu būt, ka nav.

[v3rb0]

A Latin square is an n × n table filled with n different symbols in such a way that each symbol occurs exactly once in each row and exactly once in each column

 

ja nevajag neko viltīgu, tad izstaigā pa rindām, pārbaudi vai kolonā ir visi simboli un vai tikai vienu reizi.

kad rindas beidzas, tad staigā pa kolonām, un pārbaudi tieši to pašu.

tiklīdz kaut kas pārbaudēs nesakrīt, nav vērts tālāk kaut ko pārbaudīt.

[Delfins]

Nu principā C++ viegli uztaisīt - visvienkāršākais - 4 ielikti cikli.

 

for (c)
{
for (r)
{
	 for (check_c)
	 {
		  for (check_r)
		 {
			  if (c != check_c && check_r != r && arr[r][c] == arr[check_r][check_c])
				   return false;
		 }
	 }
}
}

 

Būtība PHP to pašu dara:

1 cikls - iziet caur rindam, kolonam (2 cikli)

2 cikls - sakope vertibas, atselekte unikalus (2 cikli)

Parbaude starp uniq un reālo (3 cikls ... a moš arī izmanto hašu, tas gan jāskatās php sourcē)

Edited October 4, 2007 by Delfins

[bubu]

Kādu vēl hašu jāizmanto?

[cucumber]

Nu es domaju kaut ko tadu, tikai laikam to ciklu braek vieta labak f-ju uzmestarot ar return.
// nodrosina ievad-izvadiericu lietosanu
#include <iostream> 

//  tiks lietots vardkopu apgabals std objektiem
using namespace std;


int main(){
// maingo definicija
bool status = true;
int latin[4][4];  //masivs
unsigned int n;

latin[0][0] = 1; latin[0][1] = 2; latin[0][2] = 3; latin[0][3] = 4;
latin[1][0] = 2; latin[1][1] = 3; latin[1][2] = 4; latin[1][3] = 1;   
latin[2][0] = 3; latin[2][1] = 4; latin[2][2] = 1; latin[2][3] = 2;	
latin[3][0] = 4; latin[3][1] = 1; latin[3][2] = 2; latin[3][3] = 3;	

n = 4;


 for(int k = 0; k<n; k++){ //kolonnas cikls
	 if( !status )break;  //partraukt ciklu ja status ir veinads false  
		 for(int r = 0; r<n; r++){ //rindas cikls

			if( latin[k][r] > n){ //ja skaitlis masiva ir lielaks par izmeru, tad sads kvadrats neeksiste
			  status = false; //statusa maina  
			  break;  
			}	

		   //cikls kurs parbauda kolonnas,rindas vertibas uz sakritibu
		   for(int c=0; c<n; c++){									
			 if(  c != k && latin[k][r] == latin[c][r] ){//salidzinam tekoso skaitli ar kolonnas skaitliem, iznemot tekoso skait 
			   status = false; //statusa maina		 
			   break; //cikla partraukshana
			 }  
			 if( c != r && latin[k][r] == latin[k][c] ){//salidzinam tekoso skaitli ar rindas skaitliem, iznemot tekoso skait  
			   status = false;  //statusa maina	  
			   break; //cikla partraukshana	   
			 }				  
		   }  

		 } //rindas cikls beigas
 } //kolonnas cikls beigas	   


 cout <<  status; 

 return 1; //atgriezam 1 programmas korekti nostradajusi 
} // main funkcijas beigas

Edited October 4, 2007 by cucumber

[bubu]

Parasti pieņemts no programmas atgriezt 0, ja viss notikās korekti. Vai arī jebkuru citu vērtību (visbiežāk 1), ja kautkas notikās slikti.

[andrisp]

bubu, vai tad nebūtu normāli otrādi ? Vai arī iekš C++ ir cita prakse ?

[Delfins]

return 0 -> ERROR_CODE = 0 (nav kļūdas)

Tā ir visā winapī gandrīz (tur kur neatgriež handli)

[bubu]

Tas nav tikai C++. Tā ir visur windowsā/DOSā/Linuxī neatkarīgi no valodas.

Runa jau nav par funkcijas atgriezto bool tipa vērtību (true - viss ok, false - nav ok). Runa ir par programmas atgriezto error code, vai arī kā Delfins saka - WinAPI error kodu (vai citu API, piemēram OpenGL).

[andrisp]

Īstenībā laba pieeja, bet web projektos tās īpaši vajadzīgs gan nav.