امروز برای شما دانشجویان مهندسی نرم افزار و بازدید کننده گان عزیز یک اسلاید در مورد مربع جادویی که مرتبط با درس هوش مصنوعی می باشد آپلود کردم . امیدوارم استفاده کافی را از این مطلب داشته باشید.
برای تهیه این اسلاید کلی وقت صرف کرده ام لطفا با نظرات خود من را یاری کنید.
مساله هشت وزیر از جمله مسائل پرمخاطب مباحث طراحی الگوریتم است. ۸ مهره وزیر رو روی صفحه شطرنج چنان بچینید که نتوانند همدیگه رو تهدید کنند.
برای افرادی که با بازی شطرنج آشنایی ندارند: وزیر مهره ای از مهره های بازی شطرنجه که می تونه در تمامی ۸ جهت هر تعداد خانه – تا زمانی که مهره ای مانع نباشه – حرکت کنه و اگه در یکی از این خانه ها مهره حریف قرار داشته باشه تهدیدش کنه. مساله هشت وزیر : ما مساله رو در حالت کلی در نظر می گیریم. یعنی زمانی که ابعاد صفحه شطرنج n در n و تعداد مهره ها n هستش. ( n > 3 ) روشهای مختلفی برای پیدا کردن جواب وجود داره. یکی از این روشها چیدن تصادفی مهره ها روی صفحه شطرنجه! به عبارت دیگه n مهره رو به صورت تصادفی در خانه های مختلف صفحه قرار می دیم و بررسی می کنیم که آیا شرط مساله رو برآورده می کنن یا نه؟ این روش بسیار سریع ما رو به جواب می رسونه. اما ایرادی که داره نمی شه مطمئن بود بشه به همه حالتهای چینش دست پیدا کرد. در صفحه ۸ در ۸ شطرنج این مساله ۹۲ جواب مختلف داره. شما ممکنه روش تصادفی رو هزار بار به کار ببرید، اما نتونید همه ۹۲ حالت ممکنه رو به دست بیارید. این روش زمانی مفیده که پیدا کردن یه جواب برای ما کافی باشه. در این دسته روشها مهره ها رو یکی یکی و به صورت بازگشتی روی صفحه طوری می چینیم که مطمئن باشیم با مهره های قبلی تداخل نداره و شرط مساله برآورده می شه. معمولا از سطر اول صفحه شروع می کنیم به قرار دادن مهره ها. پر واضحه که هر سطر فقط می تونه یه مهره رو تو خودش جا بده. مهره سطر دوم رو طوری قرار می دیم که توسط مهره سطر اول تهدید نشه. برای این کار خانه های مختلفی از سطر رو می شه انتخاب کرد. برای نظم داشتن کارهامون فرض می کنیم همیشه انتخاب خانه ها از سمت چپ سطر شروع می شه. به عبارت دیگه با شروع از سمت چپ سطر اولین خانه ای که شرط رو برآورده کنه انتخاب می کنیم. به همین ترتیب سطرهای بعدی رو هم می چینیم. اگر به سطری رسیدیم که بر اساس چیدمان سطرهای قبلی هیچ خانه امنی برای مهره وجود نداشت ( یعنی همه خانه ها توسط مهره های قبلی تهدید می شدن ) یه مرحله به عقب بر می گردیم و مهره سطر قبل رو جابجا می کنیم. این کار هم با حرکت مهره به اولین خانه سمت چپ موقعیت فعلی که شرط رو برآورده کنه، انجام می شه. با ادامه دادن این روال و با جابجا کردن مهره ها به صورت منظم و بازگشتی تمامی حالتهای ممکنه به دست می یان. برای پیاده سازی چنین الگوریتمی و تشخیص اینکه چه خانه هایی از سطر امن هستن روشهای مختلفی وجود داره. ساده ترینشون اینه که هر بار تمامی خانه هایی رو که امکان تهدید شدن از اونها وجود داره بررسی کنیم تا از قرار نداشتن مهره وزیر در اونها مطمئن باشیم. اما این روش اصلا کارا و بهینه نیست. روش دیگه تعریف کردن صفحه شطرنج به صورت یه آرایه n در n هستش که خونه های امن و غیر امن با علامتگذاری مشخص می شن. هر بار که مهره ای رو صفحه قرار می گیره تمام خونه هایی که توسط این مهره تهدید می شن به صورت غیر امن علامتگذاری می شن. به این ترتیب می شه فهمید که هر خونه با توجه به چینش مهره های قبلی امن هست یا نه؟ اما این روش هم معایبی داره که باعث می شه به روش سوم رجوع کنیم. برای آشنایی با این معایب کافیه سعی کنید کد برنامه رو بنویسید! در روش سوم که من ازش استفاده کردم، برای علامتگذاری خانه های امن و غیر امن از شیوه دیگه ای بهره می بریم. به این ترتیب که اقطار راست به چپ، چپ به راست و ستونها با شماره هایی مشخص می شن که کار علامتگذاری رو بسیار ساده می کنن. این روش بدون شک از کاراترین روشهای رسیدن به جواب مساله ماست. هم سرعت اجرای بالایی داره و هم حافظه مصرفی بسیار کم! کدی که به زبان ++C درباره این مساله نوشته شده با استفاده از روش سوم تعداد جوابهای ممکن – و نه خود جوابها – برای مقادیر مختلف n رو مشخص می کنه. به عنوان مثال اگر n رو ۸ وارد کنید خروجی برنامه ۹۲ خواهد بود. توصیه می کنم برای nهای بزرگ برنامه رو امتحان نکنید! اگر n رو ۱۶ وارد کنید بعد از گذشتن زمان زیادی عدد ۱۴۷۷۲۵۱۲ روی صفحه نمایش چاپ می شه. یعنی در صفحه شطرنج ۱۶ در ۱۶ حدود ۱۵ میلیون حالت مختلف برای چیدمان صحیح وجود داره!!
در زیر نیز برای شما عزیزان لینک دانلود سورس کد این مسئله به زبان های گوناگون گذاشته شده است
در لينک زير حل مسئله 8 وزیر با زبان C قرار دارد:
لینک دانلود :
در لينک زير حل مسئله 8 وزیر با زبان ++C قرار دارد:
لینک دانلود :
در لينک زير حل مسئله 8 وزیر با زبان #C قرار دارد:
لینک دانلود :
در لينک زير حل مسئله 8 وزیر توسط الگوريتم ژنتيک با زبان VB.Net قرار دارد:
امروز برای شما دانشجویان مهندسی نرم افزار و بازدید کننده گان عزیز یک اسلاید در مورد مسئله معمای 8 که مرتبط با درس هوش مصنوعی می باشد آپلود کردم . امیدوارم استفاده کافی را از این مطلب داشته باشید.
برای تهیه این اسلاید کلی وقت صرف کرده ام لطفا با نظرات خود من را یاری کنید.
ابتدا برای نگه داری اعداد جهت مقایسه ،متغیر تعریف می کنیم، سپس اعداد یکی یکی با متغیر max
مقایسه می شوند و عدد بزرگتر در max قرار داده می شود
++c
#c
#include #include
int main() { int max = 0, i=0; int num; cout<<"\npress {a...Z} TO 'FINISH'."; cout<<"\n enter your number :"; while( cin>>num ) { max = (max < num)?num:max; } cout<<"the maximum number is : "<<max; getch(); return 0; }
using System;
using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System.Text; using System.Windows.Forms;
namespace WindowsFormsApplication1 { public partial class Form1 : Form { public Form1() { InitializeComponent(); }
cout<<"Factorial of "<<num<<" is : "<<fact; getch(); return 0; }
using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System.Text; using System.Windows.Forms;
namespace WindowsFormsApplication1 { public partial class Form1 : Form { public Form1() { InitializeComponent(); }
private void button1_Click(object sender, EventArgs e) { int num,fact=1;
main() { int x1=1,x2=1,x3,n,sum=0; cout<<"how much object of Fibonacci series want to find?\nenter here : "; cin>>n; cout<<","<<x1<<","<<x2; for(int i=3; i<=n;i++) {
x3=x2+x1; x1=x2; x2=x3; sum = sum + x3; cout<<","<<x3; } cout<<"\n Result = "<<sum; getch(); return 0; }
using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System.Text; using System.Windows.Forms;
namespace WindowsFormsApplication1 { public partial class Form1 : Form { public Form1() { InitializeComponent(); }
private void button1_Click(object sender, EventArgs e) { int x1 = 1, x2 = 1, x3, n, sum = 0; n = Int32.Parse(textBox1.Text); lbl1.Text=lbl1.Text+x1+","+x2; for (int i = 3; i <= n; i++) {
این الگوریتم ساده ترین و معروف ترین الگوریتم برای مرتب سازی داده است.
فرض کنید می‌خواهیم n داده به صورت صعودی مرتب شوند. عنصر اول را با با عنصر دوم مقایسه کرده، و در صورتی که عنصر اول بزرگتر باشد باشد جای عنصر اول و دوم را عوض می‌کنیم. همین کار را با عناصر دوم و سوم انجام می‌دهیم و همینطور عناصر سوم و چهارم ، الی آخر. وقتی این کار تمام شد بزرگترین عنصر بین داده‌ها به آخر لیست می‌رسد . حالا یک بار دیگر از اول این کار را انجام می‌دهیم اما این بار تا عنصر (n -۱)ام ادامه می‌دهیم (عنصر nام در مرحله اول در جای خودش قرار گرفته). باز هم این کار را تا عنصر (n - ۲)ام تکرار می‌کنیم ، و بازهم .... تا اینکه بالاخره داده‌ها مرتب می‌شوند.
using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System.Text; using System.Windows.Forms;
namespace WindowsFormsApplication1 { public partial class Form1 : Form { public Form1() { InitializeComponent(); } //................................................................................... int[] bubleSort(string test) { int i = 0;
int test2size = 0;
//count number's that entered in textbox by counting ',' for (i = 0; i < txt1.TextLength; i++) if (test[i] == ',') test2size++;
* که یک آرایه (arr[]) و سمت چپ ترین اندیس آرایه (Lobj) و سمت راست ترین اندیس آرایه (Robj).
تابع پارتیشن در هر مرحله اجرا ،سمت چپ ترین عنصر را(Lobj) به عنوان عنصر محوری (Pivot)انتخاب می کند و تمام عناصر بزرگتر از آن را با عناصر کوچکتر از آن تعویض می کند. آرایه ورودی پس از پایان این تابع به گونه ایست که در هر مرحله عنصر محور را در مکان اصلی اش قرار می دهد.
using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System.Text; using System.Windows.Forms;
namespace WindowsFormsApplication1 { public partial class Form1 : Form { public Form1() { InitializeComponent(); } int Partition(int[] arr, int Lobj, int Robj) { int pivot = Lobj; int temp; while(Lobj < Robj) { while(arr[Lobj] <= arr[pivot]) Lobj++;
برنامه: آرایه ای از اعداد را به روش ادغام، یا همان marge sort مرتب می کند
الگوریتم :
از دو تابع استفاده می کنیم
1 - تابع Marge Sort یا MS().
void ms(int arr[],int lx,int rx)
این تابع از عنصر lx تا عنصر rx آرایه ی arr[] را پردازش می کند.
2 - تابع sort یا sortm
void sort(int arr[],int lx,int mid1,int mid2 , int rx)
این تابع قسمت اول آرایه ی arr یعنی lx تا mid1 و قسمت دوم یعنی mid2 تا rx را مرتب کرده و در آرایه temp نتیجه را که مرتب شده ی دو قسمت فوق می باشد را ذخیره ، سپس توسط دستور زیر ، عناصر مرتب شده را در آرایه ی اصلی کپی می کند.(که mid2=mid1+1)
for(int i=0,k=lobj;i <j;i++,k++) arr[k]=temp[i];
که lobj همان lx و robj همان rx می باشد.
* تابع run در کد جاوااسکریپت ،رشته ی ورودی را به یک آرایه از اعداد تبدیل می کند.
فرمت ورودی اعدا باید به صورت زیر باشد.
example : 5,2,6,4,2,3,9,8,5,
که پس از هر عددی یک "," باید وارد شود و بدون هیچ گونه فاصله ای.
برنامه مرتب سازی ادغامی با زبان ++C
#include #include
#define size 10
void sort(int arr[],int lx,int mid1,int mid2 , int rx) { int j=0; int temp[size]; int lobj=lx,robj=rx;
//sorting arr[lx]..arr[mid] with arr[mid2]...arr[rx] and save it in temp[] while( (lx <= mid1) && (mid2 <= rx) ) { if (arr[lx] < arr[mid2]) { temp[j++]=arr[lx++]; } else{ temp[j++]=arr[mid2++]; } } while( mid2 <= rx) { temp[j++]=arr[mid2++]; } while( lx <= mid1) { temp[j++]=arr[lx++]; } //copy temp[] into the original array ( arr[] ) for(int i=0,k=lobj;i <j;i++,k++) arr[k]=temp[i]; }
int main() { int test[size] = {5,9,1,8,2,7,3,6,4,0};
cout<<"
Array is "; for(int i=0; i cout<<" "<<test[i];
ms(test,0,size-1);
cout<<"
sorted array is : "; for(int i=0; i cout<<" "<<test[i]; getch(); return 0; }
برنامه مرتب سازی ادغامی با زبان #C
using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System.Text; using System.Windows.Forms;
namespace WindowsFormsApplication1 { public partial class Form1 : Form { public Form1() { InitializeComponent(); }
void sort(int[] arr,int lx,int mid1,int mid2 , int rx) { int j=0; int[] temp = new int[arr.Length]; int lobj=lx,robj=rx;
توسط دستورات بالا جست و جو انجام می شود که در صورت یافتن، مکان قرار گیری عنصر در آرایه( i )، و اگر هم عنصر مورد نظر یافت نشد مقدا 1- را بر می گرداند
*در دو برنامه سی شارپ و جاوااسکریپت ، تابع ، ابتدا آرایه ی ورودی را به یک آرایه از اعداد تبدیل می کند سپس توسط دستورات فوق ، عمل جست و جو را انجام می دهد.
آرایه ورودی باید بدون هیچ گونه فاصله ای به این صورت وارد شود که بعد از هر عدد یک علامت کاما ( , ) قرار بگیرد.
مانند:
1,5,6,88,52,101,23,25,12,1,47,7,8,
برنامه ی جست و جوی خطی به زبان ++C
//Writed By barnamenevisi-ccj.mihanblog.com
#include #include
#define size 10
int linear_search(int arr[],int arrsize, int obj) { for(int i=0;i<arrsize;i++) { if(arr[i] == obj) { return i; } } return (-1); } main() { int test[size]={2,6,4,8,3,5,9,7,1,0}; int object; int result;
cout<<"\n\nEnter Number to search it : "; cin>>object;
result = linear_search(test,size,object); if ( result == -1) { cout<<"\nNot Find :( ."; } else{ cout<<"\nItem Founded in element "<<result+1<<" ."; }
getch(); return 0; }
برنامه ی جست و جوی خطی به زبان #C
using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System.Text; using System.Windows.Forms;
namespace WindowsFormsApplication1 { public partial class Form1 : Form { public Form1() { InitializeComponent(); } //................................................................................... int linear_search(string test,string objsearch) { int i = 0; int test2size = 0; int obj = Int32.Parse(objsearch);
for (i = 0; i < txt1.TextLength; i++) if (test[i] == ',') test2size++;
برنامه: پیدا کردن یک عدد در آرایه به روش دودویی یا Binary Search
الگوریتم:
ابتدا آرایه ی ورودی را توسط یکی از روش های مرتب سازی (به عنوان مثال مرتب سازی حبابی یا Buble Sort) که قبلا نوشته ایم ،مرتب کرده سپس با دستورات زید به جست و جو می پردازیم
int binary_search(int arr[],int arrsize,int obj) { int first = 0; int last = arrsize; int middle = (first + last) / 2;
1 - یک آرایه (مرتب شده به صورت صعودی). (اگر آرایه نزولی مرتب شده باید جای ">" , "<" را عوض کنیم)
2 - اندازه ی آرایه
3 - و عددی که باید دنباله آن بگردیم.
که در صورت پیدا کردن عدد در آرایه عنصر، اندیس آن و در غیر اینصورت عدد منفی یک ( 1- ) را بر می گرداند.
* نکات مربوط به کد سی شارپ و جاوااسکریپت
تکست باکس اول آرایه ی ورودی را با این فرمت که پس از هر عدد یک " , " باشد(بدون هیچ فاصله ای) را گرفته و در تکست باکس دوم عددی را که باید به دنبال آن بگریم از ورودی می گیریم.
} //-----------------------Binary Search------------------------------------- int binary_search(int arr[],int arrsize,int obj) { int first = 0; int last = arrsize; int middle = (first + last) / 2;
int test[size]={10,19,12,18,15,17,11,14,13,16}; int searchobj=0; int flag;
//sort array bubleSort(test,size-1);
cout<<"Enter number to search : "; cin>>searchobj;
flag = binary_search(test,size-1,searchobj);
if(flag != -1) cout<<"\nfind item in element "<<flag+1<<" ."; else cout<<"\nnot found.";
getch(); return 0; }
برنامه ی جست و جوی دودویی به زبان #C
using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System.Text; using System.Windows.Forms;
namespace WindowsFormsApplication1 { public partial class Form1 : Form { public Form1() { InitializeComponent(); } //-----------------------Binary Search------------------------------------- int binary_search(int[] arr, int arrsize, int obj) { int first = 0; int last = arrsize; int middle = (first + last) / 2;
دستور بالا تک جمله های دنباله ی بالا را به ترتیب از n=0 تا .... محاسبه و آنها را در متغیر result جمع می کند.
به این ترتیب Ln عدد محاسبه می شود و در نهایت در تابع Log با استفاده از فرمول ، لگاریتم را محاسبه می کنیم.
*حاصل جملات دنباله ی فوق به ازی n های بزرگتر ، کوچکتر می شود لذا با توجه به شرط حلقه ی While ،زمانی از حلقه ی While خارج می شیم که اختلاف جمله ی فعلی از جمله ی قبلی به حداقل که رسیده باشه.در اینجه یک ضربدر ده به توان منفی 11.(هرچه این مقدار کوچکتر باشد حاصل دقیق تر هست.)
برنامه: نمایش درخت دودویی با استفاده از آرایه توضیحات :
یک درخت دودویی رو به دو صورت میشه نمایش داد 1 - نمایش با آرایه 2 - نمایش با لیست پیوندی
در این قسمت نمایش درخت دودویی با استفاده از ارایه رو می خوایم پیاده کنیم. همونطور که می دونید در این روش ،ریشه رو در خانه اول ارایه قرار میدیم و از قانون زیر پیروی می کنیم
* اگر عنصری در خانه ی i ام ارایه باشد آنگاه پدر ان در خانه ی جزوصحیح i/2 قرار دارد. فرزند چپ آن در خانه ی 2*i قرار دارد. فرزند راست آن در خانه ی 1+2*i قرار دارد.
*برای نمایش درختی با عمق k به ارایه ای با 2k-1 خانه نیاز داریم.
درخت ورودی را به صورت زیر از ورودی میگیریم.((فرزند راست ، فرزند چپ)پدر)
(F(B(A,D(C,E)),G(,I(H))))
الگوریتم:
تابع set آرایه ی []s که حاوی رشته ی فوق هست را به همراه ارایه ی []t که قرار هست درخت طبق قوانین بالا در ان ذخیره شود و متغیری که اندازه ی ارایه []s را در خود دارد را از ورودی گرفته و با چند دستور if عملیات را انجام می دهد.
برنامه ی نمایش درخت با ارایه به زبان ++c
void set(char s[],char[] t,int sSize) { int i=0; int j=0; int depth=1,oldDepth=1;
من هادی مومنی دانشجوی کارشناسی نرم افزار کامپیوتر و به زبان برنامه نویسی و طراحی صفحات وب تسلط دارم خوشحال میشم کمکتون کنم لطفا نظراتتون در مورد بهتر شدن این وبلاگ بگید.
عضو شوید
عضویت سریع
آمار مطالب
آمار بازدید
