برنامه: پیدا کردن یک عدد در آرایه به روش دودویی یا 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;
من هادی مومنی دانشجوی کارشناسی نرم افزار کامپیوتر و به زبان برنامه نویسی و طراحی صفحات وب تسلط دارم خوشحال میشم کمکتون کنم لطفا نظراتتون در مورد بهتر شدن این وبلاگ بگید.