42-3(برج هانوی)

هر متخصص مبتدی علوم کامپیوتری حتما درگیر مسائل کلاسیک خاص شده است.مسئله ی برج های هانوی از معروف ترین مسائل علوم کامپیوتر می باشد.طبق یک روایت افسانه ای کشیشانی در معبدی از شرق سعی می کنند پشته ای از چند دیسک رااز یک میله به میله ای دیگر انتقال دهند. پشته ی اولیه ی دارای 64 دیسک می باشد که روی یک میله قرار گرقته اند و اندازه ی دیسک ها از پایین به بالا به ترتیب نزولی مرتب شده اند.کشیشان می خواهند این پشته را از یک میله به میله ای دیگر انتقال دهند به شرطی که اولا در هر مرحله فقط یک دیسک جابه جا شود و هیچ موقع نباید دیسک بزرگ تر بالای دیسک کوچک تر قرار گیرد.میله ی سوم نیز برای نگهداری موقف دیسک ها استفاده شده است.گفته می شود  زمانی که کشیشان کار خود را به پایان برسانند پایان جهان فرا می رسد. بنابراین انگیزه ی زیادی در اسان کردن کار ان ها نیست.

#include<iostream>

#include<conio.h>

using namespace std;

void towers(int, int, int, int);

int main()

{

int nDisks;

cout << "Enter the starting number of disks: ";

cin >> nDisks;

towers(nDisks, 1, 3, 2);

getch();

return 0;

}

void towers(int disks, int start, int end, int temp)

{

if (disks == 1) {

cout << start << "  --> " << end << '\n';

return;

}

//move disks - 1 disks from start to temp

towers (disks - 1, start, temp, end);

//move last disks from start to end

cout << start << "  --> " << end << '\n';

//move disks - 1 disks from temp to end

towers(disks - 1, temp, end, start);

}

جست و جوی دودویی

در این تمرین می توانید با جست و جوی دو دویی(باینری) اشنا می شویم.

#include<iostream>

#include<conio.h>

#include<iomanip>

using namespace std;

int binarySearch(int [], int, int, int, int);

void printHeader(int);

void printRow(int [], int, int, int, int);

int main()

{

const int arraySize = 15;

int a[arraySize], key, result;

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

a[i] = 2 * i;

cout << "Enter a number between 0 to 28: "; 

cin >> key;

printHeader(arraySize);

result = binarySearch(a, key, 0, arraySize - 1, arraySize);

if(result != -1)

cout << '\n' << key << " found in array element "

    << result << endl;

else

cout << '\n' << key << " not found" << endl;

getch();

return 0;

}

//binarry search

int binarySearch(int b[], int searchKey, int low, int high, int size)

{

int middle;

while(low <= high){

middle = (low + high) / 2;

printRow(b, low, middle, high, size);

if(searchKey == b[middle])

return middle;

else if (searchKey < b[middle])

high = middle - 1;

else

low = middle + 1;

}

return -1;

}

//print a header for the output

void printHeader(int size)

{

cout << "\nSubscripts:\n";

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

cout << setw(3) << i << ' ';

cout << '\n';

for(int i = 1; i <= 4 * size; i++)

cout << '-';

cout << endl;

}

//...................

void printRow(int b[], int low, int mid, int high, int size)

{

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

if(i < low || i > high)

cout << "      ";

else if(i == mid)

cout << setw(3) << b[i] << '*';

else

cout << setw(3) << b[i] << ' ';

cout << endl;

}

جست و جوی خطی: جست و جوی دو دویی

جست و جوی ارایه ها: جست و جوی خطی

در جست و جوی خطی هر عنصر از ارایه با کلید جست و جو مقایسه می شود.چون ارایه به ترتیب خاصی نیست احتمال یافتن مقدار مورد نظر در اولین عنصر با احتمال یافتن ان در اخرین عنصر یکسان است. بنابراین برنامه باید کلید جست و جو را به طور متوسز با نیمی از عناصر ارایه مقایسه کند تا مقدار مورد نظر را پیدا کند. اگر مقدار مورد مزبور در ارایه وجود نداشته باشد برنا مه باید کلید جست و جو را با همه ی عناصر ارایه مقایسه کند تا این موضوع را بفهمد.

** روش جست و جوی خطی برای ارایه های کوچک یا ارایه های مرتب نشده مناسب است برای برای ارایه های بزرگ روش کارامدی نیست.

با استفاده از یک برنامه که در ان از این شیوه استفاده شده است با کاربرد و نحوه ی ییاده سازی ان اشنا می شویم.

---

 #include<iostream>

#include<conio.h>

using namespace std;

int linearSearch( const int [], int, int);

int main()

{

const int arraySize = 100;

int a[arraySize], searchKey, element;

for(int x = 0; x < arraySize; x++)

a[x] = 2 * x;

cout << "Enter integer search key:" << endl;

cin >> searchKey;

element = linearSearch(a, searchKey, arraySize);

if(element != -1)

cout << "Found value in element " << element << endl;

else

cout << "Value not found" << endl;

getch();

return 0;

}

//%%%%%%%%%%%

int linearSearch(const int array[], int key, int sizeOfArray)

{

for(int n = 0; n < sizeOfArray; n++)

if(array[n] == key)

return n;

return -1;

}

مرتب کردن ارایه ها

مرتب کردن ارایه ها

مرتب کردن داده ها (یعنی قرار دادن داده ها به ترتیبی خاص مثلا صعودی یا نزولی) یکی از مهم ترین کاریرد ارایه هاست. بانک ها همه ی چک ها را به ترتیب شماره ی حساب مرتب می کنند تا بتوانند در پایان هر ماه  ریز حساب هر فرد را تهیه کنند. شرکت های تلفن فهرست مشترکین خود را به ترتیب نام خانوادگی و در داخل ان  به ترتیب نام مرتب می کنند تا یافتن شماره ی تلفن ها اسان شود. تقریبا هر سازمانی باید داده هایی(و در بسیاری از اوقات مقدار معتناهی داده) را مرتب کند. مرتب کردن داده ها مساله جالبی است و تحقیقات گسترده ای را در زمینه ی علوم کامپیوتری به خود جلب کرده است. در این فصل درباره ی ساده ترین شیوه ی مرتب کردن بحث خواهد شد در تمرین ها شیوه های پیچیده تری را که کارایی بهتری از خود نشان می دهند مورد بررسی قرار خواهیم داد. 

35-3 یادگیری جدول ضرب با کامپیوتر

کامپیوتر نقش بسزایی را در امر اموزش ایفا می کند. برنامه ای به زبان ++C بنویسید که به یادگیری جدول ضرب به دانش اموزان مقطع ابتدایی کمک نماید. این برنامه باید دو عدد صحیح یک رقمی را با استفاده از rand تولید و سوالی به شکل زیر برای کاربر نمایش دهد:

                                                                              How much is 6 time 7?

سپس دانش اموز باید پاسخ را وارد کند. برنامه پس از بررسی پاسخ در صورت درست بودن عبارت "Very good" را نمایش دهد . سوال دیگری مطرح نماید در غیر این صورت برنامه عبارت "No. Please try again" را نمایش داده و بار دیگر به دانش امز فرصت دهد تا نهایتا پاسخ درست را دریافت کند.

#include<iostream>

using std::cout;

using std::endl;

using std::cin;

#include<cstdlib>

#include<ctime>

void multipilication(void);

int main()

{

srand(time(0));

multipilication();

return 0;

}

//++++++++++++++++++++

void multipilication (void)

{

int x, y, response = 0;

cout << "Enter is -1 to End.\n";

while(response != -1) {

x = rand() % 10;

y = rand() % 10;

cout << "How much is " << x << " time " << y << " (-1 to End)? ";

cin >> response;

while(response != -1 && response != x * y) {

cout << "No. Please try again.\n? ";

cin >> response;

}

if(response != -1)

cout << "Very good!\n\n";

}

cout << "That's all for now. Bye." << endl;

}