لینک دانلود و خرید پایین توضیحات
دسته بندی : وورد
نوع فایل : word (..doc) ( قابل ویرایش و آماده پرینت )
تعداد صفحه : 23 صفحه
قسمتی از متن word (..doc) :
1
زوج مرتب :
تعریف : مجموعه ی دو عضوی که در آن جابه جایی وجود ندارد زوج مرتب گفته می شود و به صورت (b،a) نشان داده می شود و در زوج مرتب جابه جایی وجود ندارد
در زوج مرتب (b،a)a را مولفۀ اول و b را مؤلفۀ دوم می نامیم.
یک کاربرد زوج مرتب استفاده از آن برای نمایش مختصات یک نقطه در صفحه است
نماد (yوx)a را به معنای نقطه ای در صفحه در نظر می گیریم که طول آن برابر x و عرض آن برابر y است.
تساوی دو زوج مرتب : شرط لازم و کافی برای اینکه دو زوج مرتب (b،a)(d،c) با هم برابر باشند این است که (d=b ، c=a)
مولفه های اول با هم برابر باشند و مولفه های دوم هم با هم برابر باشند .
مثال : به ازای کدام مقادیر x و y دو زوج مرتب (y-x و 16) و (2و) برابرند ؟
2
مثال : مقادیر x وy را چنان بیابید که در نقطه ی بر هم منطبق باشند ؟
چون دو نقطه با هم منطبق هستند پس باید مولفه های اول و دوم با هم برابر باشند.
حاصلضرب دکارتی :
تعریف : هرگاه A و B دو مجموعه دلخواه باشند حاصلضرب دکارتی .دو مجموعه A وB که آنرا با علامت B×A نشان می دهیم مجموعه همه زوج های مرتبی است که مولفه های اول آغاز از A مولفه های دوم آغاز از B باشد.
تذکر : هرگاه مجموعه a دارای m عضو و مجموعه b دارای n عضو باشد B×A و A×B دارای m.n عضو هستند.
در حاصلضرب دکارتی جابجایی وجود ندارد
مثلاً : اگر
دکارتی مجموعه در خودش
3
مثال :
اگر و B×A را مشخص کنید و نمودار مختصاتی B×A را رسم کنید ؟
برای رسم نمودار B×A هر عضو آن را به عنوان مختصات یک نقطه در نظر می گیریم و در صفحه رسم میکنیم .
مثال : اگر نمودار B×A را در صفحه نمایش دهید ؟
4
مثال : اگر و B×A را مشخص کنید.
مثال : حاصل ضرب دکارتی هر یک از مجموعه های زیر را دستگاه رسم کنید ؟
َ
لینک دانلود و خرید پایین توضیحات
دسته بندی : پاورپوینت
نوع فایل : powerpoint (..ppt) ( قابل ویرایش و آماده پرینت )
تعداد اسلاید : 14 اسلاید
قسمتی از متن powerpoint (..ppt) :
بنام خدا
File Structure
بازیابی سریع داده ها – مرتب ساز ی (Finding data quickly – Sorting)
روشها ی بازیابی سریع داده ها چگونه میباشند؟
یادآور ی جستجوی دودویی ( Binary Searching )؟
مقایسه با جست وجوی سری( sequential )؟
محدودیت ها یا معایب جست و جوی دودویی کدامند ؟
مرتب سازی کلیدها ( key sorting ) چگونه است؟
روش Indexing چیست؟
مزایای Indexing کدامند؟
File Structure
بازیابی سریع داده ها
روشها ی بازیابی سریع داده ها چگونه میباشند؟
یادآور ی جستجوی دودویی ( Binary Searching )؟
مثال:
یک فایل با رکورد های به طول ثابت را در نظر میگیریم.
فرض کنیم که در جست و جوی رکوردی با مقدار کلیدی مشخصی میباشیم.
حالت اول: اگر فایل مرتب ن شده باشد :
بایستی رکورد ها ی آنرا یک به یک خوانده و کلید آنها را با مقدار مورد نظر مقایسه کنیم .
این کار ممکن است به خواندن کلیه رکورد ها منتهی شود. (چرا؟)
حالت دوم: اگر فایل بر حسب کلید مورد نظر مرتب شده باشد :
روش بهینه همان جست و جوی دودویی میباشد . (چرا؟)
الگوریتم آن در شکل 13-6 کتاب موجود است. ( با اشتباه چاپ ی ! )
File Structure
بازیابی سریع داده ها
یادآور ی الگوریتم جستجوی دودویی :
int BinarySearch
(FixedRecordFile & File, RecType & obj, KeyType & key)
{
int low = 0; int high = file.NumRecs()-1;
While (low
{
int guess = (high + low) / 2;
file.ReadByRRN (obj, guess);
if (obj.Key() == key) return 1;
if (obj.Key()
else high = guess - 1;
}
return 0;
}
low
RRN
high
0
1
3
n
....
....
File Structure
بازیابی سریع داده ها
مقایسه با جست وجوی سری( sequential )؟
مثال:
جستجو ی کلید در یک فایل با تعداد 2000 = n رکورد .
حالت اول: جست و جوی سری :
تعداد ماکزیمم رکورد های خوانده شده برابر با تعداد کل رکورد ها خواهد بود.
ممکن است تا 2000 رکورد خوانده شود.
اگر تعداد رکورد ها دوبل شود ، تعداد خواندن رکورد نیز دوبل خواهد شد . (چرا؟)
حالت دوم: جست و جوی دودویی :
تعداد ماکزیمم رکورد های خونده شده برابر با 1+log(n) خواهد بود.
ممکن است تا 1+log(2000) یعنی 11 رکورد خوانده شود.
اگر تعداد رکورد ها دوبل شود ، فقط یک خواندن رکورد اضافه می گردد.
برا ی جست و جوی دودویی بای ستی طول رکورد ها ثابت باشد. (چرا؟)
لینک دانلود و خرید پایین توضیحات
دسته بندی : پاورپوینت
نوع فایل : powerpoint (..ppt) ( قابل ویرایش و آماده پرینت )
تعداد اسلاید : 45 اسلاید
قسمتی از متن powerpoint (..ppt) :
بنام خدا
1
مرتب سازی سریع Quicksort
ساختمان داده ها و الگوریتمها
2
Quicksort
Hoare در سال 1962 پیشنهاد کرده است
از روش تقسیم و حل (Divide & Conquer) استفاده می کند
آرایه را به صورت “در جا” (In Place) مرتب می کند
شبیه مرتب سازی درجی (Insertion Sort) است.
برخلاف (Merge Sort ) به حافظه اضافی نیاز ندارد.
پیاده سازی های سریعی که برای آن ارائه شده، باعث بکارگیری وسیع آن در عمل شده است.
3
تقسیم و حل
تقسیم:یک عضو مثل x از آرایه را انتخاب کرده و آرایه را طوری به دو بخش طوری تقسیم می کنیم که یک بخش آن از x کوچکتر و بخش دیگر از x بزرگتر باشند.
x
>= x
حل: به صورت بازگشتی هر کدام از این دو بخش را مرتب می کنیم
ترکیب: کارخاصی لازم نیست!
نکته: هزینه عمل تقسیم خطی است Θ(n)
4
تقسیم
هزینه تقسیم برای آرایه n عضوی برابر Θ(n) است
PARTITION(A, p, q) // A[p. . q]
x←A[p] // pivot= A[p]
i←p
for j←p+ 1 to q
do if A[j] ≤x
then i←i+ 1
swap A[i] ↔A[j]
swap A[p] ↔A[i] // final place of pivot!
return i
5
لینک دانلود و خرید پایین توضیحات
دسته بندی : وورد
نوع فایل : word (..doc) ( قابل ویرایش و آماده پرینت )
تعداد صفحه : 23 صفحه
قسمتی از متن word (..doc) :
1
زوج مرتب :
تعریف : مجموعه ی دو عضوی که در آن جابه جایی وجود ندارد زوج مرتب گفته می شود و به صورت (b،a) نشان داده می شود و در زوج مرتب جابه جایی وجود ندارد
در زوج مرتب (b،a)a را مولفۀ اول و b را مؤلفۀ دوم می نامیم.
یک کاربرد زوج مرتب استفاده از آن برای نمایش مختصات یک نقطه در صفحه است
نماد (yوx)a را به معنای نقطه ای در صفحه در نظر می گیریم که طول آن برابر x و عرض آن برابر y است.
تساوی دو زوج مرتب : شرط لازم و کافی برای اینکه دو زوج مرتب (b،a)(d،c) با هم برابر باشند این است که (d=b ، c=a)
مولفه های اول با هم برابر باشند و مولفه های دوم هم با هم برابر باشند .
مثال : به ازای کدام مقادیر x و y دو زوج مرتب (y-x و 16) و (2و) برابرند ؟
2
مثال : مقادیر x وy را چنان بیابید که در نقطه ی بر هم منطبق باشند ؟
چون دو نقطه با هم منطبق هستند پس باید مولفه های اول و دوم با هم برابر باشند.
حاصلضرب دکارتی :
تعریف : هرگاه A و B دو مجموعه دلخواه باشند حاصلضرب دکارتی .دو مجموعه A وB که آنرا با علامت B×A نشان می دهیم مجموعه همه زوج های مرتبی است که مولفه های اول آغاز از A مولفه های دوم آغاز از B باشد.
تذکر : هرگاه مجموعه a دارای m عضو و مجموعه b دارای n عضو باشد B×A و A×B دارای m.n عضو هستند.
در حاصلضرب دکارتی جابجایی وجود ندارد
مثلاً : اگر
دکارتی مجموعه در خودش
3
مثال :
اگر و B×A را مشخص کنید و نمودار مختصاتی B×A را رسم کنید ؟
برای رسم نمودار B×A هر عضو آن را به عنوان مختصات یک نقطه در نظر می گیریم و در صفحه رسم میکنیم .
مثال : اگر نمودار B×A را در صفحه نمایش دهید ؟
4
مثال : اگر و B×A را مشخص کنید.
مثال : حاصل ضرب دکارتی هر یک از مجموعه های زیر را دستگاه رسم کنید ؟
َ
لینک دانلود و خرید پایین توضیحات
دسته بندی : پاورپوینت
نوع فایل : powerpoint (..ppt) ( قابل ویرایش و آماده پرینت )
تعداد اسلاید : 30 اسلاید
قسمتی از متن powerpoint (..ppt) :
بنام خدا
آرایه ها و مرتب سازی
ساختمان داده ها و الگوریتمها
آرایه
آرایه مجموعه ای محدود و معین از عناصر هم نوع است
مثال : ,5] [1 ,2,3,4
اعضای آرایه به صورت صریح تعریف می شوند
آرایه با اعضای آن به صورت کامل مشخص می شود
تعاریف ریاضی و مفهومی مانند “ مجموعه اعداد اول کوچکتر از 100” در اینجا استفاده نمی شود
اعمال روی آرایه
ساخت آرایه: شامل اختصاص حافظه به تعداد معین و از نوع معین است:
X = Create_Array(‘integer’ , 100);
دسترسی برای مقدار دهی به آرایه از طریق یک اندیس و عملگر [] انجام می گیرد: x[2] = 5
خواندن مقدار آرایه هم با همین عملگر میسر است: y = x[34]
جستجو در آرایه و مرتب سازی آن به منظور جستجوی سریعتر، مهمترین اعمال سطح بالای آرایه هستند
مرتب سازی
مرتب سازی
برای یافتن یک عضو خاص، باید تمام اعضای آرایه را بازبینی کرد. برای آرایه های خیلی بزرگ این کار زمان زیادی می برد
اگر آرایه مرتب شد باشد یعنی یک رابطه ترتیب مثل : for all i , j if i
مثال: برای یافتن عضو (3) تنها کافی است نیمه اول آرایه [1 2 3 4 5 7 9 10] را بازرسی کنیم.
معمولا مرتب سازی یکبار انجام می گیرد و پس از آن، افزودن اعضای جدید به آرایه با الگوریتم هایی که ترتیب را حفظ می کنند، انجام می شود.
الگوریتم بکار رفته برای مرتب سازی ممکن است بسیار زمانبر یا پر مصرف باشد. بنابراین سعی بر این است که الگوریتمهایی طراحی کنیم که هزینه کمتری داشته باشند
الگوریتم طراحی شده و برنامه نوشته شده باید :
درست باشد.
از منابع موجود به نحو مناسب استفاده کند.
با برنامه های دیگر بنحو مسالمت آمیز اجرا شود.
پیاده سازی آن راحت باشد.
یک الگوریتم مرتب سازی
void anysort(int [] A){
int N = A.length ;
int flag = 1 ;
while (flag ==1 ){
flag = 0 ;
for (int k=0 ; k
if (A[k] > A[k+1] ){
int temp = A[k] ;
A[k] = A[k+1] ;
A[k+1] = temp ;
flag = 1 ;
}
}
}
هزینه
C1
C2
C3
C4
C5
C6
C7
C8
C9
C10
تکرار
1
1
N
N
N
N(N-1)
N(N-1)
N(N-1)
N(N-1)
N(N-1)