الگوریتمهای برنامه نویسی از ساده به پیشرفته

[اشک]

با سلام.امیدوارم دوستان همراهی کنند تا این تاپیک بار علمی زیادی رو ایجاد کنه.سعی می کنم که از هرسه روش حل مسئله(DP.D&C.GREEDY) کدهایی رو بذارم.

الگوریتمINSERTION SORT

ابتدا لیستی از اعداد را که داده شده در نظر می گیریم و عدد مورد نظر را که باید به لیست اضافه شود در مکانی موقت (TEMP)قرار می دهیم.بعد به ترتیب از آخر لیست شروع می کنیم به مقایسه کردن عدد موجود در لیست وTEMP. اگر عدد مورد نظر از TEMPبزرگتر بود آن را یک خانه به جلو شیفت می دهیم.اما اگر کوچکتر بود آنرا جایگزین خانه ی جلویی می کنیم.

پیاده سازی در c#.net

کد php:

using system;
using system.collections.generic;
using system.text;
namespace insertionsort
{
class program
{
static void main(string[]args)
{
insertion();
}
//*********************insertion sort****************
public static void insertion()
{
float [] A=new float[6];
console.writeline("please enter five members:");
console.writeline("\n");
for(int j=1;j<=5;g++)
{
string str=console.readline();
float f=float.parse(str);
A[j]=f;
console.writeline("array["+j+"]"+"="+ A[j]+ "\n");
}
console.writeline("your array is :"+"\n");
for (int k=1;k<=5;k++)
{
console.writeline("array[(0)]=(1)", k , a[k]);
}
console.write("\n");
console.write("**************insertion sort************");
console.writeline("\n");
for(int p=2;p<=5;p++)
{
float temp=A [p];
int q=p-1;
while (q>0&&A[q]>temp)
{
A[q+1]=A[q];
q--;
}
A[q+1]=temp;
}
for(int q=1;q<=5;q++)
{
console.writeline("sort array[(0)] = (1)",q,A[q]);
}
console.write("\n");
console.write("*****************END*************");
console.write("\n");
console.readline();
}
}
} 


---

پیاده سازی در c++

کد php:

#include<iostream.h>
#include<conio.h>
class insertionsort
{
public:
float A[5];
void sort(float *A);
};
void insertionsort::sort(float* A)_
{
for(int p=2;p<=5;p++)
{
float temp=A[p];
int q=p-1;
while(q>0 && A[q]>temp)
{
A[q+1]=A[q];
q--;
}
A[q+1]=temp;
}
}
int main()
{
clrscr();
float A[5];
insertrionsort IS;
cout<<"please Anter 5 Number:"<<andl;
for(int i=1;i<=5;i++)
{
int n;
cin>>n;
A[i]=n;
}
cout<<"\n";
cout<<"your array is :{";
for(int j=1;j<5;j++)
{
cout<<A[j]<<",";
}
cout<<A[5]<<"}"<<"\n";
cout<<"\n"<<"***************insertionsort*****************"<<"\n";
cout<<"\n";
IS.sort(A);
cout<<"your sorted Array As:{";
for(int k=1;k<5;k++)
{
cout<<A[k]<<",";
}
cout<<A[5]<<"}"<<"\n\;
getch();
} 


[اشک]

اینم الگوریتم binary search

کد php:

void binry serch(int *A,int n,int x,int &j)
{
int low=i;high=n;mid,j=0;
while(low<=high){
mid=(low+high)/2;
if(x<A[mid])
high=mid-1;
else if(x>[mid])
low=mid+1;
else{
j=mid;
return n;
}
}
} 


[اشک]

این الگوریتم ضرب یا multهست که با استفاده از روش DANDCحل شده.و ضرب دو عدد n بیتی رو بیان می کنه.

کد php:

int mult (int x,int y, int n)
{
int s;
int m1,m2,m3;
int A,B,C,D;
S=sign(x)*sign(y);
x=ABS(x);y=ABS(y);
if(n==1){
if(x==1)&&(y==1)
return(S);
else
return(0);
}
else
{
A=left(x,n/2);
B=reght(x,n/2);
C=left(y,n/2);
D=right(y,n/2);
m1=mult(A,c,n/2);
m2=mult(A-B,D-C,n/2);
m3=mult(B,D,n/2);
return(S*leftshift(m1,n)+leftshift(m1+m2+m3,n/2)+m3));
}
} 


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

[HoseinVig]

سلام کار خوبیو شروع کردی
اما یا باید عنوان تاپیک رو عوض کنی یا بجای کد الگوریتم بزاری

[اشک]

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

[t3r!p3000]

اجازه هست سوال بپرسیم !

عدد های خیلی بزرگ رو چجوری با هم ضرب می کنن !
چون جواب تو یه متغیر جا نمیشه !! ( حتی متغیر 64 بیتی )

شنیدم با آرایه این کارو می کنن !

فقط نمی دونم چجوری ؟؟؟

یکم توضیح بدین خوبه !

طوری که من بتونم رو میکرو هم پیاده کنم !
آخه میکرو محدودیت زیاد داره !
فضای استک محدوده , تابع برگشتی نمی تونم کار کنم , متغیر هام تا 32 بیت عملکرد خوبی دارن - سرعت کمه - مقدار رم و حافظه هم محدوده و ....

یکی از جاهایی که به مشکل خوردم : http://forum.iranled.com/showthread.php?...#pid114199

[اشک]

سلام.علی عزیز من درست نمی دونم.اما چیزی که به ذهنم خطور می کنه اینه:
می تونیم عدد رو در یک مبنای خاص مثلا 2 ببریم.و چون میگی تو میکرو محدودیت زیاده شاید بهتره از همین مبنا استفاده کنی.چون هم سمبلها کمترن و .. خلاصه برای طراحی خوبه.و بعد یک آرایه باتوجه به بزرگی عددت انتخاب کنی و هرکدوم از رقمها رو توی آرایه بچینی.بعد یک کد لازمه.که وقتی می خوای عدد رو بخونی یا ازش استفاده کنی و یا بحالت اصلی برگردونی باید اون کد اجرا شه.کار اون کد اینه که عددت رو که در مبنای 2هست و در آرایه ذخیره کردی رو به مبنای 10 میبره و عدد اصلی دوباره ایجاد میشه.و هروقت خواستی عددت رو توی آرایه ذخیره کنی باید عکس اون کد رو بذاری.یعنی بردن عدد از مبنای 10 به مبنای 2.

---

اینم پیاده سازی :merge sort

کد php:

#include<iostream>
using namespace std;
void merge(float *B,int i,int m,int j){
float *temp=new float[j-i+1];
int s1=i,s2=m+1; 
int k=0;
while((s1<=m)&&(s2<=j)){
if(B[s1]<B[s2])
temp[k++]=B[s1++];
else
temp[k++]=B[s2++];
}
while(s1<=m)
temp[k++]=B[s1++];
while(s2<=j)
temp[k++]=B[s2++];
while(k>0)
B[j--]=temp[--k];
delete[] temp;
}
void mregesort(float *A,int p,int q){
int mid;
if(p<q){
mid=(p+q)/2;
mergesort(A,p,mid);
mergesort(A,mid+1,q);
merge(A,p,mid,q);
}
}
int main(){
float c[]={11.2,21.3,3.4,2.1,51.7,19.2,12.8,6.3,4.8,10.9,9.6};
mergesort(c,0,10);
for(int i=0;i<=10;i++)
cout<<endl<<"c["<<i<<"]="<<c[i];
return 0;
} 


در merge sort مرتب سازی صورت می گیره.بصورت زیر:
عددی رو انتخاب می کنیم.بعد اون رو در خانه ی آخر که خالی هست کپی می کنیم.حالا مقایسه انجام می گیره.عددی رو که داریم با تمامی ساب لیست مقایسش می کنیم رو توی تمپ می ذاریم.به ترتیب اعداد رو با تمپ مقایسه می کنیم.اگر عنصر مقایسه شونده کوچکتر از تمپ بود تمپ رو جلوی عنصر کپی می کنیم.اگرنه خود عنصر رو در خانه ی جلویی کپی کرده و به عنصر بعدی می پردازیم..

[اشک]

اینم الگوریتم all-paths که معروفه به floyd

کد php:

void all-paths(int *cost,int *A,int n)
{
int i,j,k;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
A[i,j]=cost[i,j];
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(A[i,j]>(A[i,k]+A[k,j]))
A[i,j]=A[i,k]+A[k,j]
} 


زمان اجرای این الگوریتم تتای n به توان 3هست.ماتریس بدست آمده در پایان الگوریتم،همان طول کوتاهترین مسیر بین i,j می باشد.

[اشک]

الگوریتم یافتن ماکزیمم اول و دوم از بین عناصر یک آرایه

کد php:

void maxF_s(A,p,q,maxF,maxs){
if(p==q){maxF=maxs=A[p];}
else if(p==q-1){
if(A[p]<A[q]){maxF=A[q],maxs=A[p];}
else{maxF=A[p],maxs=A[q];}
}
else{
m=[(p+q)/2];
maxF_s(A,p,m,maxF l,maxs l);
maxF_s(A,m+1,q,maxF r,maxs r);
maxF=maximum(maxF l,maxF r);
if(maxF==maxF r)
maxs=maximum(maxF l,maxs r);
else
maxs=maximum(maxF r,maxs l);
}
} 


[اشک]

اینم پیاده سازی الگوریتم quick sort

کد php:

#include<iostream>
using namespace std;
int partition(float*,int,int);
void swap(float *,float*);
void quicksort(float* A,int p,int q)
{int r;
if (p<q){
r=partition(A,p,q);
quicksort(A,p,r-1);
quicksort(A,r+1,q);
}
}
int partition(float* A,int p,int q){
float x;
int i;
x=A[q];
i=p-1;
for(int j=p;j<=q-1;j++){
if(A[j]<=x){
i++;
swap(&A[i],&A[j]);
}
}
swap(A[i+1],A[q]);
return i+1;
}
void swap(float* y1,float* y2){
float temp=*y1;
*y1=*y2;
*y2=temp;
}
int main(){
float B[8]={12.1,8.6,18,5,14.2,19,14.8,8.6}
for(int i=0;i<8,i++)
cout<<endl<<"B["<<i<<"]="<<B[i];
quicksort(B,0,7);
cout<<endl<<"*****************quicksort*************";
for(i=0;i<8;i++)
cout<<endl<<"B["<<i<<"]="<<B[i];
return 0;
} 


[اشک]

پیاده سازی الگوریتم فیبوناچی:

کد:

#include<iostream>
#include<conio>
using namespace std;
class FIBO
{
public:
int fibo(int n);
};
int FIBO::fibo(int n)
{
if(n<=2)
return 1;
else
return(fibo(n-1)+fibo(n-2));
}
int main()
{
clrscr();
int number,result;
cout<<"please enter your number:";
cin>>number;
cout<<"\n";
FIBO f;
result=f.fibo(number);
cout<<"the output of your function is:";
cout<<result;
getch();
}