آموزش برنامه نویسی c++ - آموزش و سورس برنامه ی سی پلاس پلاس

[poor!a 15130]

آرایه یک بعدی به عنوان آرگومان تابع:

 

در زبان c++ همانگونه که میتوانیم انواع متغیر ها را به عنوان آرگومان به یک تابع ارسال کنیم، آرایه ها نیز میتوانند به عنوان آرگومان به توابع ارسال شوند. برای ارسال آرایه به تابع، باید نام آرایه به عنوان آرگومان ذکر شود. اگر آرایه به عنوان آرگومان تابع باشد، پارامتر معادل آن میتواند بصورت زیر تعریف شود:

1. آرایه با طول مشخص

2. آرایه با طول نامشخص که در این صورت بهتر است طول آرایه به آرگومان دیگری منتقل شود.

3. اشاره گر که میتوان اشاره گری به یک آرایه تعریف نمود.(در جلسات آینده با اشاره گر ها کاملا آشنا خواهید شد.)

 

شکل کلی ارسال آرایه به توابع:

 

void f1(int x[]);

void f2(int x[], int len);

 

void main()

{

int x[10];

f1(x);

f2(x,10);

}

void f1(int x[10])

{

...

}

void f2(int x[], int len)

{

...

}

 

//end

[poor!a 15130]

مرتب سازی آرایه ها (Sort):

 

عمل مرتب سازی در کامپیوتر، عمل بسیار مهمی محسوب میشود و بسیاری از روش های مرتب سازی باید بر روی آرایه ها انجام شود، از این رو الگوریتم های بسیاری برای مرتب سازی آرایه ها طراحی شده است. این الگوریتم ها از الگوریتم های ساده تا پیچیده طراحی شده اند و هم اکنون نیز تحقیقات برای بهبود روش های مرتب سازی ادامه دارد.

 

برای مرتب سازی آرایه یک بعدی، روش های مختلفی همچون روش مرتب سازی حبابی (Bubble Sort)، انتخابی (Selection Sort)، سریع (Quick Sort)، درجی (Insertion Sort)، ادغامی (Merge Sort) و ... وجود دارد که در تمامی روش های فوق تفاوت در روش مقایسه و جابجایی است، که باعث شده الگوریتم های متفاوتی تولید شوند.

در این بین الگوریتم مرتب سازی حبابی بسیار ساده و قابل فهم است.

 

در پست های آینده، توابع اکثر روش های مرتب سازی گذاشته خواهد شد.

[poor!a 15130]

 

الگوریتم مرتب سازی حبابی که متوسط عملکرد آن O(n²) است:

 

 

void BubbleSort(int temp[], int len)

{

int i, j, item;

for(i=len-1;i>0;i--)

for(j=0;j

if(temp[j]>temp[j+1])

{

item=temp[j];

temp[j]=temp[j+1];

temp[j+1]=item;

}

}

 

 

//end

[poor!a 15130]

تابع مرتب سازی انتخابی(Selection Sort) که متوسط عملکرد آن О(n²) است:

 

void selectionSort(int arr[], int len)

{

int i, j, minIndex, tmp;

for (i = 0; i

{

minIndex = i;

for (j = i + 1; j

if (arr[j]

minIndex = j;

if (minIndex != i)

{

tmp = arr;

arr = arr[minIndex];

arr[minIndex] = tmp;

 

}

 

}

 

}

 

//end

[poor!a 15130]

 

تابع مرتب سازی سریع(Quick Sort) که متوسط عملکرد آن O(n log n) است:

 

void quickSort(int x[], int left, int right)

{

 

int i = left, j = right;

 

int tmp;

 

int pivot = x[(left + right) / 2];

 

 

while (i

{

 

while (x

 

i++;

 

while (x[j] > pivot)

 

j--;

 

if (i

{

 

tmp = x;

 

x = x[j];

 

x[j] = tmp;

 

i++;

 

j--;

 

}

 

}

 

 

if (left

 

quickSort(x, left, j);

 

if (i

 

quickSort(x, i, right);

 

}

 

 

//end

[poor!a 15130]

سورس برنامه ی حل معادله ی درجه دوم با گرفتن a و b و c:

 

 

#include

#include

 

void main()

{

int a, b, c;

int delta;

cout

cin>>a>>b>>c;

delta = (b*b)-(4*a*c);

if(delta == 0)

{

cout

}

else if(delta > 0)

{

cout

cout

}

}

 

 

//end

[poor!a 15130]

 

تابع مرتب سازی درجی(Insertion Sort) که متوسط عملکرد آن О(n²) است:

 

 

void insertionsort ( int arr[] , int n)

{

int i , j , x;

for (i=2 ; i

{

x = arr ;

j= i-1;

while( j>0 && arr [j] > x)

{

arr[j+1] = arr [j];

j--;

}

arr[j+1]=x;

}

}

 

//end

[poor!a 15130]

 

مرتب سازی ادغامی، حل مسئله را به چند قسمت تبدیل کرده و آن ها را جدا حل میکند. به همین سبب از چندین تابع برخوردار است و متوسط عملکرد آن از رابطه O(n log n) بدست می آید.

 

 

void mergeSort(int numbers[], int temp[], int array_size)

{

m_sort(numbers, temp, 0, array_size - 1);

}

 

 

void m_sort(int numbers[], int temp[], int left, int right)

{

int mid;

 

if (right > left)

{

mid = (right + left) / 2;

m_sort(numbers, temp, left, mid);

m_sort(numbers, temp, (mid+1), right);

 

merge(numbers, temp, left, (mid+1), right);

}

}

 

void merge(int numbers[], int temp[], int left, int mid, int right)

{

int i, left_end, num_elements, tmp_pos;

 

left_end = (mid - 1);

tmp_pos = left;

num_elements = (right - left + 1);

 

while ((left

{

if (numbers

{

temp[tmp_pos] = numbers

;

tmp_pos += 1;

left += 1;

}

else

{

temp[tmp_pos] = numbers[mid];

tmp_pos += 1;

mid += 1;

}

}

 

while (left

{

temp[tmp_pos] = numbers

;

left += 1;

tmp_pos += 1;

}

while (mid

{

temp[tmp_pos] = numbers[mid];

mid += 1;

tmp_pos += 1;

}

 

//modified

for (i=0; i

{

numbers

= temp

;

right -= 1;

}

}

 

 

//end

[poor!a 15130]

در حال حاضر دارم تمام روش های مرتب سازی رو که میشناسم، معرفی کنم.(که در کل 20 تا میشه!)

بازم میگم که اگه سوال یا درخواست پروژه ای داشتید، به رایگان مینویسیم.(در حد توانم)

مباحث آتی رو هم میگم که دوستان منتظر باشن:

- آرایه های چند بعدی

- رشته های کاراکتری

- اشاره گر ها

- سطوح ذخیره سازی و کلاس های حافظه

- وکتور ها

- مرجع

- کلاس ها

- بارگذاری اپراتور ها

- مقدمه برنامه نویسی شی گرا

- وراثت

- ریخت زایی

- ...

 

بازم هست!

 

بعد اگه عمری بود میریم سراغ مبحث شی گرایی

[poor!a 15130]

 

 

تابع مرتب سازی سطلی یا صندوقی(Bucket Sort) که متوسط عملکرد آن (O(n است:

 

 

void bucketSort(int a[],int n, int max)

{

int* buckets = new int[max];

int SIZE = n;

for(int j = 0 ; j

buckets[j] = 0;

for(int i = 0 ; i

++buckets[a];

for(i = 0 , j = 0 ; j

for(int k = buckets[j] ; k > 0 ; k--)

a[i++] = j;

}

 

//end

[poor!a 15130]

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

 

 

... ,21, 13, 8, 5, 3, 2, 1, 1, 0

 

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

 

int f ( int x)

{

if ((x==1)||(x==2))

return 1;

else if (x==0)

return 0;

else

return f(x-1)+f(x-2);

}

 

 

//end

 

 

[poor!a 15130]

تابع مرتب سازی شمارشی (Counting Sort) که متوسط عملکرد آن O(n + k) است:

 

 

void countingSort(vector

& arr)

{

int Min, Max;

Min = Max = arr[0];

for(int i = 1; i

{

if(arr

Min = arr;

 

if(arr > Max)

Max = arr;

}

int Range = Max - Min + 1;

 

vector Count(Range,0);

 

for(int i = 0; i

Count[arr - Min] ++;

 

int Index = 0;

for(int i = Min; i

for(int j = 0; j

arr[index ++] = i;

}

 

 

//end

[poor!a 15130]

 

تابع الگوریتم مرتب سازی هرمی (Heap Sort) که متوسط عملکرد آن O(n log n) میباشد:

 

 

void fnSortHeap(int arr[], int ubound)

{

int i,o;

int lChild, rChild, mChild, root, temp;

root = (ubound-1)/2;

for(o=root;o>=0;o--)

{

for(i=root;i>=0;i--)

{

lChild = (2*i)+1;

rChild = (2*i)+2;

if ((lChild

{

if(arr[rChild] >= arr[lChild])

mChild = rChild;

else

mChild = lChild;

}

else

{

if(rChild > ubound)

mChild = lChild;

else

mChild = rChild;

}

if (arr

{

temp = arr;

arr = arr[mChild];

arr[mChild] = temp;

}

 

}

 

}

 

temp = arr[0];

arr[0] = arr[ubound];

arr[ubound] = temp;

return;

}

 

 

//end

[poor!a 15130]

تابع روش مرتب کردن کوکتل (Cocktail Sort) که بدترین عملکرد آن از رابطه ی О(n²) بدست می آید:

 

void cocktail_sort (int Arr[], int n)

{

int left = 0, right = n;

bool finished;

do

{

finished = true;

--right;

for (int i = left; i

if (Arr > Arr[i+1]) {

swap(Arr, Arr[i+1]);

finished = false;

}

if (finished) return;

finished = true;

for (int i = right; i > left; i--)

if (Arr

swap(Arr, Arr[i-1]);

finished = false;

}

++left;

} while (!finished);

}

 

 

//end

[poor!a 15130]

تابع الگوریتم مرتب سازی شانه ای (Comb Sort) که بدترین عملکرد آن O(n log n) میباشد:

 

void combsort(int *arr, int n)

{

float shrink_factor = 1.247330950103979;

int gap = n, swapped = 1, swap, i;

 

while ((gap > 1) || swapped)

{

if (gap > 1)

gap = gap / shrink_factor;

 

swapped = 0;

i = 0;

 

while ((gap + i)

{

if (arr - arr[i + gap] > 0)

{

swap = arr;

arr = arr[i + gap];

arr[i + gap] = swap;

swapped = 1;

}

++i;

}

}

}

 

//end

[poor!a 15130]

 

تابع مرتب سازی شل یا پوسته ای (Shell Sort) که بدترین عملکرد آن O(nlog²n) است:

 

 

void shellsort(int A[],int max)

{

int stop,swap,limit,temp;

int x=(int)(max/2)-1;

while(x>0)

{

stop=0;

limit=max-x;

while(stop==0)

{

swap=0;

for(int k=0;k

{

if(A[k]>A[k+x])

{

temp=A[k];

A[k]=A[k+x];

A[k+x]=temp;

swap=k;

}

}

limit=swap-x;

if(swap==0)

stop=1;

}

x=(int)(x/2);

}

}

 

//end

[poor!a 15130]

تابع روش مرتب سازی گورزاد (Gnome Sort) که بدترین عملکرد آن O(n²) است:

 

 

void gnomeSort(int arr[], int n)

{

int i = 0, temp;

 

while( i

{

 

if ( i == 0 || arr [i - 1]

i++;

 

else

{

temp = arr;

arr = arr[i - 1];

arr[--i] = temp;

}

 

}

 

}

 

//end

[poor!a 15130]

در این روش بدون در نظر گرفتن اینکه آرایه مرتب یا نامرتب است، عنصر مورد جستجو با هر یک از عناصر آرایه مقایسه میشود.

 

 

int linearSearch(int arr[], int len, int pat)

{

for(int i=0;i

if(arr==pat)

return i;

return -1;

}

 

//end

[poor!a 15130]

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

 

 

int binarySearch(int arr[], int len, int pat)

{

int mid, low=0, high=len-1;

while(low

{

mid=(low+high)/2;

if(pat

high=mid-1;

else if(pat>arr[mid])

low=mid+1;

else

return mid;

}

return -1;

}

 

//end

[poor!a 15130]

آرایه های چند بعدی:

 

در زبان C++ این امکان وجود دارد که آرایه های چند بعدی تولید نماییم. به روش زیر:

 

;...[تعداد عناصر بعد سوم] [تعداد عناصر بعد دوم] [تعداد عناصر بعد اول] نام آرایه نوع آرایه

 

 

بیشترین کاربرد آرایه ها در برنامه نویسی به آرایه های دو بعدی مربوط است.

 

آرایه های دو بعدی:

 

آرایه های دو بعدی یا ماتریس به شکل زیر تعریف میشوند:

 

;...[تعداد عناصر بعد دوم] [تعداد عناصر بعد اول] نام آرایه نوع آرایه

 

چون تعریف آرایه ی دو بعدی همان تعریف یک ماتریس در زبان C++ است، لذا تعداد عناصر بعد اول بیانگر تعداد سطر های ماتریس و تعداد عناصر بعد دوم بیان کننده ی تعداد ستون های ماتریس است. یعنی اندیس اول آرایه مشخص کننده شماره سطر و اندیس دوم مشخص کننده ی شماره ی ستون است.

 

مثال:

int a[2][3];

 

//end

 

نکته: در زبان C++ ذخیره شدن آرایه در حافظه بصورت سطری است. یعنی ابتدا عناصر سطر اول و سپس عناصر سطر دوم و ... در حافظه ذخیره می شوند.