PDA

View Full Version : الگوریتم مربع جادویی



ghasedak404
شنبه 14 آبان 1384, 01:52 صبح
به سلام خدمت همه دوستان عزیز
کی می تونه الگوریتم مربع جادویی رو بنویسه ؟
مربع جادویی یه ماتریس n * n هست که اعضای اون اعداد 1 , 2 , 3 , ... , n هستند که هر کدوم یک بار تکرار می شن و مجموع سطرها ، ستون ها و قطرهاش برابر هست . مثل مربع جادویی 5*5 :

15 8 1 24 17

16 14 7 5 23

22 20 13 6 4

3 21 19 12 10

9 2 25 18 11

ab_ba
شنبه 14 آبان 1384, 07:53 صبح
آیا این از لحاظ ریاضی ثابت شده است
یعنی به ازای هر عدد n یک چنین ماتریسی وجود دارد

seyedof
شنبه 14 آبان 1384, 10:11 صبح
سلام
فکر کنم به ازای n>=3 وجود داره. به عنوان یک راهنمایی الگوریتم برای n های زوج و فرد متفاوته و الگوریتم فردش نسبتا آسونه ولی برای زوج پیچیده تر است.
ممنون علی

ghasedak404
یک شنبه 15 آبان 1384, 01:05 صبح
سلام
آره . برای n های فرد ساده تر هست . از نظر ریاضی هم ثابت شده هست . اصلا یکی از مباحث ریاضیه .
حالا کسی هست حلش کنه ؟

someCoder
یک شنبه 15 آبان 1384, 23:58 عصر
توی مربع خودت دقت کنی میفهمی: از 1 شروع کن و بصورت ضربدری به سمت بالا سمت راست حرکت کن. دقت کنی میفهمی

ghasedak404
دوشنبه 16 آبان 1384, 09:27 صبح
سلام somecoder

آره دقیقا همین طوره . من هم به این نتیجه رسیدم .

حالا کسی می تونه با پاسکال برنامشو بنویسه ؟

البته ببخشید که اینجا مطرحش کردم .

bahane274
چهارشنبه 05 اردیبهشت 1386, 14:38 عصر
سلام ! الگوریتم این برنامه این طوریه که :1-عدد 1 را در خانه وسط در سطر اول مینویسیم.2-عدد بعدی را در خانه ای که شماره سطر و ستون آن یک واحد کم تر از مختصات خانه فعلی است یادداشت میکنیم ، اگر خانه فعلی بر روی حاشیه جدول قرار داشته باشد امکان حرکت به خانه بعدی وجود ندارد زیرا از محدوده جدول خارج میشود . در این گونه موارد جدول را به صورت یک استوانه در نظر میگیریم (مثلا در مورد عدد 2 چون بالای 6 و بیرون جدول میرود آن را پایین مینویسیم)
اگر خانه بعدی پر بود از خانه فعلی به خانه ای که شماره سطر آن یک واحد بیشتر از شماره سطر خانه فعلی است حرکت میکنیم .
تعداد سطر و ستون این ماتریس باید فرد باشد . مثلا 3*3 آن این طوری میشود : 8 1 6
3 5 7
4 9 2

bahane274
یک شنبه 09 اردیبهشت 1386, 12:11 عصر
سلام ! توضیحی که دادم برای ghasedak404 بود . اشتباه از من بود که نقل قول نگذاشتم . در مورد شما هم متاسفانه نمی توانم کمکی کنم اما اگر تستی پیدا کردم حتما شما را در جریان می گذارم . موفق باشید .

setare2007
جمعه 14 اردیبهشت 1386, 09:16 صبح
سلام
دیدم همگی به این برنامه نیاز دارید منم اونو در اختیارتون میزارم
البته با پاسکاله


uses
crt;
var
a:array[1..10,1..10]of byte;
row,col,i,j,n,x,y:integer;
begin
clrscr;
write('Enter number(odd): ');
readln(n);
writeln;
row:=1;
col:=n div 2+1;
for i:=1 to n do
for j:=1 to n do
a[i,j]:=0;
a[row,col]:=1;
for i:=2 to n*n do
begin
row:=row-1;
col:=col-1;
if(row=0) then
row:=n;
if(col=0) then
col:=n;
if(a[row,col]=0) then
a[row,col]:=i
else
begin
if (row>=n) and (col>=n) then
begin
row:=row-n;
col:=col-n;
end;
row:=row+2;
col:=col+1;
a[row,col]:=i;
end;
end;
for x:=1 to n do
begin
for y:=1 to n do
begin
if (a[x,y]>=1) and (a[x,y]<=9) then
write(' ');
write(' ',a[x,y]);
end;
writeln;
end;
readln;
end.

majid_hamdi
چهارشنبه 30 اردیبهشت 1388, 23:40 عصر
با سلام خدمت همه دوستان
اگه كسي مي تونه هم الگوريتم مربع جادويي(3*3) و هم مساله 8 وزير را به زبان پرولوگ حل كنه و به من كمك كنه ممنون ميشم .

3tareha3moni
دوشنبه 08 تیر 1388, 15:22 عصر
با سلام خدمت همه دوستان
اگه كسي مي تونه هم الگوريتم مربع جادويي(3*3) و هم مساله 8 وزير را به زبان پرولوگ حل كنه و به من كمك كنه ممنون ميشم .


من هم همين سوال را دارم؟:اشتباه::متفکر:

Arcsinos
چهارشنبه 11 فروردین 1389, 19:01 عصر
سلام لطفا pdf رو ببینید .
اگه 4*4 رو دارید بهم بگید .

jlover
پنج شنبه 12 فروردین 1389, 11:17 صبح
چه جالب
منم این الگوریتم رو زمانیکه قسمت آرایه ها رو تموم کردم به عنوان تمرین آخر فصل پیاده سازی کرده بودم ( با جاوا ).
امیدوارم به دردتون بخوره :



/**
*
* author Esmaeil Ashrafi <>
*/
public class MagicSquare {
private String state = new String();

public MagicSquare() {
}

public String getState () {
return state ;
}

/**
* determines there is repeated numbers in the table or not
* @param a - the two dimensional array indicates the table
* @return true if table doesnt have any repeated number
*/
public boolean hasRepeated ( int[][] a ) {
/* java.util.Vector v = new java.util.Vector();
for (int i=0 ; i < a.length ; i++ )
for (int j=0 ; j < a.length ; j++ ){
v.addElement( new Integer(a[i][j]) );
if( v.indexOf(a[i][j]) != v.lastIndexOf(a[i][j]) )
return true ;
}
return false ;
*/
// another algorithm,more complicated,but maybe maybe more sufficient
for (int i=0 ; i < a.length ; i++ )
for (int j=0 ; j < a.length ; j++ )
for (int m=0 ; m <= i ; m++ )
for (int n=0 ; n < a.length ; n++ )
if ( a[i][j] == a[m][n] && !(m==i && n==j) )
return true;
return false;

}

public boolean isMagic( int[][] arr ) {
for(int i=0; i<arr.length; i++)
if ( arr.length != arr[i].length ){
state = "Not a square table";
return false;
}
for (int i=0 ; i < arr.length ; i++ )
for (int j=0 ; j < arr.length ; j++ )
if ( arr[i][j] < 1 || arr[i][j] > arr.length*arr.length ){
state = "some numbers out of range";
return false;
}
if ( hasRepeated(arr) ) {
state="the table has repeated numbers";
return false;
}
/* total : total value should every row,column or diagonal has
* row : total value of a row
* col : total value of a column
* ldt : left top 2 right diameter buttom toal value
* ldt : right top 2 left diameter buttom toal value
* r : row number
* c : colomn number
*/
int total , row , col , ldt , rdt , r , c ;
total=row=col=ldt=rdt=0;
/*
* set the value of sum of first row values 2 total
* and then compares every row and colomn to this value
*/
for(int i=0 ; i < arr.length ; i++ )
total+=arr[i][0]; // value of the first row
for (int i=0 ; i < arr.length ; i++ ) {
for (int j=0 ; j < arr.length ; j++ ) {
row+=arr[i][j]; col+=arr[j][i];
}
// if row==total and col==total,then row+col is 2*total
if ( (row+col) != (2*total) ){
state = "row and column values mismatch in row and column " + (i+1) ;
return false ;
}
row=col=0;
}
for (int i=0 ; i < arr.length ; i++ ) {
ldt+=arr[i][i];
rdt+=arr[i][arr.length-i-1];
}// calculates both diameter
if ( rdt+ldt != 2*total ){
state = "diameters values mismatch";
return false ;
}
return true ;
}

public static void main(String[] args){
System.out.println("\n*******************result of exercise 'Magic Square' :");
int[][] s = { {6,7,2},{1,5,9},{3,8,4} };
for(int i=0;i<s.length;i++){
for(int j=0;j<s[i].length;j++)
System.out.print(s[i][j]+" ");
System.out.println();
}
MagicSquare ms = new MagicSquare();
if ( ms.isMagic(s) )
System.out.println("Congratulation ! It's magic");
else
System.out.println( ms.getState() );
}
}



در ضمن این برای n*n هست.( البته n*n نباشه هم حتمن یه پیغامی میده )
اگه کسی ایرادی پیدا کرد(یعنی یه جدول داد و نتیجه ی غلط برگردوند بهم بگه،اینو خیلی وقت پیش نوشتم،احتمالن ایرادی نداره چون حتمن خودم 10 رقم تستش کردم...اگه داشت حتمن یادم میموند بعدن برطرفش کنم.ولی خب کار دیگه :چشمک:
---------------------
بچه ها من الان داشتم با خودم فکر میکردم منظور شما احتمالن ساختن یک مربع جادویی بوده ...
این برنامه میاد یک ماتریس m*n رو در قالب یه آرایه میگیره و تشخیص میده که جادویی هست یا نه !
پس شرمنده م .

nima898
دوشنبه 16 فروردین 1389, 12:38 عصر
سلام ! الگوریتم این برنامه این طوریه که :1-عدد 1 را در خانه وسط در سطر اول مینویسیم.2-عدد بعدی را در خانه ای که شماره سطر و ستون آن یک واحد کم تر از مختصات خانه فعلی است یادداشت میکنیم ، اگر خانه فعلی بر روی حاشیه جدول قرار داشته باشد امکان حرکت به خانه بعدی وجود ندارد زیرا از محدوده جدول خارج میشود . در این گونه موارد جدول را به صورت یک استوانه در نظر میگیریم (مثلا در مورد عدد 2 چون بالای 6 و بیرون جدول میرود آن را پایین مینویسیم)
اگر خانه بعدی پر بود از خانه فعلی به خانه ای که شماره سطر آن یک واحد بیشتر از شماره سطر خانه فعلی است حرکت میکنیم .
تعداد سطر و ستون این ماتریس باید فرد باشد . مثلا 3*3 آن این طوری میشود :
8 1 6
3 5 7
4 9 2

حرکت از 6 به 7 در مربع 3*3 مطابق این الگوریتم نیست
مربع 5*5 هم مطابق این الگوریتم نیست حرکت از ( 5 به 6 و 10 به 11 و 15 به 16 و 20 به 21 )

qwerty11
دوشنبه 16 فروردین 1389, 23:10 عصر
حرکت از 6 به 7 در مربع 3*3 مطابق این الگوریتم نیست
مربع 5*5 هم مطابق این الگوریتم نیست حرکت از ( 5 به 6 و 10 به 11 و 15 به 16 و 20 به 21 )
نه درسته. خونه ی بالا و سمت چپ عدد 6 خالی نیست (عدد 4 تو اون خونه هستش) پس مجبوریم یه خونه بیایم پایین.

mohandes ehsan
چهارشنبه 21 دی 1390, 12:14 عصر
لطفا درمورد عملكرد الگوريتم ماژيك كمكم كنيد.

POORYAII
پنج شنبه 21 آذر 1392, 20:00 عصر
سلام ببخشید من کد برنامه نویسی این برنامه مربع جادویی رو گیر اوردم ولی اگه میشه یه نفر برام توضیح بده که خط به خط این کد چیکار میکنه یعنی مثلا میگه یک سطر میری بالا بعدش یک ستون میری راست کدوم خط هستش دقیقا:

#include <conio.h>
#include<iostream>
#include <stdlib.h>
#include<time.h>
using namespace std;




int main()

{

srand(time(0));

int a;

char ch;

do

{

system("cls");



cout<<"yek adade fard vared konid : ";

cin>>a;

while(a%2==0)

{

cout<<"\nadad bayad fard bashad : ";

cin>>a;

}

int **x;

x=new int *[a];

for(int i=0;i<a;i++)

x[i]=new int [a];



for(int i=0;i<a;i++)

for(int j=0;j<a;j++)

x[i][j]=0;



int i=0;int j=((a-1)/2);



for(int k=1;k<=(a*a);k++)

{



///////////////////////

if(i>=a)

i=i-a;

if(j>=a)

j=j-a;

if(i<0)

i=i+a;

if(j<0)

j=j+a;

//////////////////////

if(x[i][j]!=0)

{

i=i+2;

j++;

}

///////////////////////

if(i>=a)

i=i-a;

if(j>=a)

j=j-a;

if(i<0)

i=i+a;

if(j<0)

j=j+a;

///////////////////////

x[i][j]=k;

i--;

j--;

}

cout<<"\n";

for(int i=0;i<a;i++)

{

for(int j=0;j<a;j++)

cout<<x[i][j]<<" ";

cout<<"\n\n";

}

cout<<"edame midahid? yes(y) ya no(n) : ";

cin>>ch;

cout<<"\n";

}while(ch=='y');



getch();

return 0;

}


در اینجا میبینیم که آرایه پویا هم تعریف شده ئ این کد به درستی کامپایل و اجرا میشه ولی مثلا کدی که اعداد رو به صورت ماتریس میچینه و cout میکنه کدوم هست؟ "/n"/n هستش؟

majid.fe
دوشنبه 26 اسفند 1392, 21:30 عصر
به این وبلاگ هم سر بزنین شاید به دردتون بخوره:
http://decoding.blogfa.com/
(http://decoding.blogfa.com/)

darknes666
چهارشنبه 28 اسفند 1392, 01:38 صبح
سلام خدمت همه ی دوستان عزیز.
این سوال شما سوز زخم منو بیشتر کرد.ولی به هر حال دنیاست...


به این وبلاگ هم سر بزنین شاید به دردتون بخوره:
http://decoding.blogfa.com/
(http://decoding.blogfa.com/)
دوست عزیز اگر پاسخ سوال رو میدونی مستقیم بزار اینجا.برای افزایش بازدید وبلاگت پاسخو از منابع اینگیلییش میزاری تو وبلاگ بعد میایی اینجا لینک میدی.چه کاریه آخه؟

بگذریم.این جدول یکی از الگوریتم های مزخرفش امتحان کردن تمامی حالت هاست که معلومه بهینه نیست و به کامپیوتر قویی نیاز داره.
من سورس کد حل جدول رو ندارم ولی الگوریتمشو میدونم که براتون میگم.
برای هر عدد فردn یک روش خیلی معروف وجود داره که توضیح میدم.
میمونه اعداد زوج.برای اعداد زوج شما کافیه ی یه دونه روش حل 4 رو بدونی و یه دونه 6.
چراکه 4 مضارب 4 رو حل میکنه و 6 هم اعدادی به فرم n=4k+2 و عملا شما مساله رو برای تمامی اعداد حل کردی یعنی 4k,4k+1,4k+2,4k+3
دوتا از اونا که فرد هستن و دوتای دیگرو هم که توضیح دادم.

خب بریم سراغ الگوریتم اعداد فرد:
اول براتون 3*3 رو حل میکنم.بعد 5*5 و بقیه ی اعداد فرد مثل همینا حل میشه.

جدول 3*3 رو که بهتون داده شده به شکل زیر در بیارین.(میدونم جدولم خیلی جالب نیست)
117127
حالا به صورت زیر پرش کنین
117129
حالا اعداد رو به صورت زیر انتقال بدین و خونه های اضافی رو حذف کنین
117130
در آخر:
117131
برای 5*5 رو تو پست بعد میگم.

darknes666
چهارشنبه 28 اسفند 1392, 01:59 صبح
به خاطر محدودیت تعداد عکس ها مجبورم 5*5 رو جدا بگم.
اول 5*5 رو به شکل زیر در بیارین و پرش کنین:
117132
حالا انتقالشون به صورت زیر هست که من فقط بعضی ها رو رنگی کردم که متوجه بشین:
117133
بعد از حذف کردن به شکل زیر میشه:
117134
خب اینم از 5*5
4*4 و 6*6 رو هم تو پست بعد میگم که قاطی نشه.

darknes666
چهارشنبه 28 اسفند 1392, 11:20 صبح
خیلی خب بریم سراغ 4*4:
اول جدول رو مثل شکل زیر پر کنین:
117138
حالا کافیه خونه هایی رو که تو شکل رنگی نیستن با مکملشون جابجا کنین.(که من این جابجا کردم)

در آخر داریم:
117147
خیلی خب میتونین ببینین که جدول کامل شده.

حالا بریم سراغ 8*8 که مضرب 4 هست.
جدول و مثل زیر مقدار دهی کنین:
117148
خونه های رنگی دست نخورده میمونن.فقط جای اعداد مکمل رو عوض کنین یعنی اعدادی که حاصل جمعشون 65 میشه مثل 63 و 2.
در آخر:
117149
اینم از این.در پست بعدی برای n=4k+2 رو توضیح مختصر میدم.

darknes666
چهارشنبه 28 اسفند 1392, 14:40 عصر
حالا بریم سر N=4k+2 این از همشون بیشتر کار میبره.
شما برای حل این اول باید بدونین چجوری میشه برای اعداد فرد رو با متد Siamese حل کرد.به ویکی پدیا برین کاملا مشخصه که روشش چجوریه.
http://en.wikipedia.org/wiki/Siamese_method

خب حالا که متد Siamese رو یاد گرفتین وقتشه بریم 6*6 رو حل کنیم.
اول جدول رو به چهار تا مربع 3*3 تقسیم کنین و مطابق شکل به ترتیب زیر با الگوریتم Siamese جدول ها رو با اعداد مورد نظر پر کنین.
به شکل زیر دقت کنین:
117154
در آخر اگر توجه کنین.مجموع همه ی ستون ها باهم برابر هست اما قطر ها و سطر ها نه.
چاره اینه که شما اعداد رو به صورت ستونی جابجا کنین تا به حالت مطلوب رسین.به شکل های زیر دقت کنین:
117155
برای مثال تو ستون اول میخوایم مجموع اعداد سطر اول بشه 111 ولی در حال حاضر مجموع اعداد سطر اول برابر 84 هست ولی اگر عدد 8 رو با 35 به صورت ستونی جابجا کنین مجموع برابر میشه با 8-35+84=111 به همین ترتیب برین جلو و قطر هاهم در آخر درست میشن.
نوشتن الگوریتم این قسمت مقداری سخته شما در واقع دو راه دارین 1-امتحان تمامی حالت ها به صورت جابجایی با ستون و راه دوم استفاده از مقداری هوش مصنوعی.
اینم برای حالت 10*10
117158
جالب اینه که به مدت 180 سال تصور میشد مربع جادیی 10*10 وجود نداره.

تشکر یادتون نره.
موفق و پیروز باشین.

havakili
دوشنبه 21 اردیبهشت 1394, 13:23 عصر
با سلام به همه دوستان
میدونم که سوالم تکراریه ولی همه جا رو سرچ کردم ولی جواب نگرفتم
خوب سوالم از این قراره که:
من میخوام تمامی حالات جدول 4 تایی رو بدست بیارم؟ تمامی حالت
خوب باید این رو چه جوری انجام بدم که تمامی حالات چک بشه که دقیقا و دقیقا همه حالات مربع جادوئی بدست آید؟
لطفا راهنمائی کنید خیلی خیلی واجبه
با تشکر از همه بزرگورارن