وبلاگ رسمی مهدی غلامی میاندهی

حل مسئله ی 8 وزیر به زبان ++C

در این بازی ما باید هشت وزیر را به گونه ای در صفحه شطرنج بچینیم که هیچ یک از وزیرها، 7 وزیر دیگر را تحدید نکند.

امروز سورس مسئله 8 وزیر را به دو روش بازگشتی و غیر بازگشتی برای شما آماده کردم، امیدوارم از این برنامه بهره ببرید.

این سورس ماتریس بالا و پایین مثلثی را بدست آورده و چاپ می کند و این سورس به زبان ++C نوشته شده است .

If  J>I => X[I,J]=0

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

مثلث خیام-پاسکال(نیوتن-پاسکال)

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

...

مثلث خیام-پاسکال مثلثی از اعداد است که هر عدد از جمع دو عدد بالای خودبدست می آید.

از این مثلث می توانید در محاسبه عبارتهای مختلفی استفاده کنید.

مثلا در محاسبه حاصل عباراتی چون (a+b)ⁿ. عدد های این مثلث ضرایب عبارات هستند.

                                                                  1                (a+b)⁰

                                                               11               (a+b)¹

                                                               121              (a+b)²

                                                               1331             (a+b)³

                                                                                        ...  

مثلا برای محاسبه(a+b)^۶به ردیف هفتم مثلث مراجعه می کنیم که و از اعداد آن به عنوان ضرایب ساتفاده می کنیم.

(a+b)⁶=a⁶+6a⁵b+15a⁴b²+20a³b³+15a²b⁴+6ab⁵+b⁶

در زیر نیز برای شما عزیزان لینک دانلود سورس کد این مسئله به زبان های گوناگون گذاشته شده است


در لينک زير حل مسئله 8 وزیر با زبان C قرار دارد:

لینک دانلود :

در لينک زير حل مسئله 8 وزیر با زبان ++C قرار دارد:

لینک دانلود :

در لينک زير حل مسئله 8 وزیر با زبان #C قرار دارد:

لینک دانلود :

در لينک زير حل مسئله 8 وزیر توسط الگوريتم ژنتيک با زبان VB.Net قرار دارد:

لینک دانلود :

این هم آدرس منبعی که به دردتون می خوره

نظر یادتون نره

در این بازی ما باید هشت وزیر را به گونه ای در صفحه شطرنج بچینیم که هیچ یک از وزیرها، 7 وزیر دیگر را تحدید نکند.

 • دانلود از سرور ParsSpace

• دانلود از سرور Pico File

این سورس برای تبدیل عدد در مبنای 10 به مبنای 16 نوشته شده است.

نکته : این سورس تبدیل Decimal به Hexadecimal را انجام می دهد.

• دانلود از سرور ParsSpace

• دانلود از سرور Pico File

این سورس برای تبدیل عدد در مبنای 2 به مبنای 8 نوشته شده است.

نکته : این سورس تبدیل Binary به Octal را انجام می دهد.

• دانلود از سرور ParsSpace

• دانلود از سرور Pico File

این سورس برای تبدیل عدد در مبنای 2 به مبنای 16 نوشته شده است.

نکته : این سورس تبدیل Binary به Hexadecimal را انجام می دهد.

• دانلود از سرور ParsSpace

• دانلود از سرور Pico File

این سورس برای تبدیل عدد در مبنای 2 به مبنای 10 نوشته شده است.

نکته : این سورس تبدیل Binary به Decimal را انجام می دهد.

• دانلود از سرور ParsSpace

• دانلود از سرور Pico File

این سورس برای تبدیل عدد در مبنای 10 به مبنای 2 نوشته شده است.

نکته : این سورس تبدیل Decimal به Binary را انجام می دهد.

• دانلود از سرور ParsSpace

• دانلود از سرور Pico File

این پست به ساخت مثلث خیام به صورت نامحدود می باشد.

برنامه به این صورت پیاده سازی شده است که ابتدا عددی را از کاربر دریافت می کند و تا عدد دریافتی مثلث را تشکیل میدهد.

مثال:

۱

۱۲

۱۲۳

۱۲۳۴

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

... ,۲۱, ۱۳, ۸, ۵, ۳, ۲, ۱, ۱, ۰

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

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);

    { 

این سورس سری فیبوناچی (Fibonacci) می باشد که هم به صورت بازگشتی و هم به صورت معمولی نوشته شده است.

در ریاضیات، سری فیبوناچی (Fibonacci number) به دنباله‌ای از اعداد می‌گویند که به‌صورت زیر تعریف می‌شود:

F ( n ) := { 1 if n = 1 ; F ( n − 1 ) + F ( n − 2 ) if n > 1

غیر از دو عدد اول، اعداد بعدی از جمعِ دو عددِ قبلیِ خود به‌دست می آید. اولین اعداد این سری عبارت‌اند از:

۱، ۱، ۲، ۳، ۵، ۸، ۱۳، ۲۱، ۳۴، ۵۵، ۸۹، ۱۴۴، ۲۳۳، ۳۷۷، ۶۱۰، ۹۸۷، ۱۵۹۷، ۲۵۸۴، ۴۱۸۱، ۶۷۶۵، ۱۰۹۴۶، ۱۷۷۱۱، ۲۸۶۵۷، ۴۶۳۶۸

روش غیر بازگشتی

روش بازگشتی

الگوریتم فشرده سازی و کد گذاری هافمن

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

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

بطور مثال :

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

# توضیحات:
- Node: ساختار برای درخت هافمن که گره‌ها را نمایش می‌دهد.
- compare: ساختار برای مقایسه گره‌ها در صف اولویت.
- printCodes: تابعی که کدهای هافمن را با استفاده از درخت تولید می‌کند و آنها را چاپ می‌نماید.
- HuffmanCoding: تابع اصلی که درخت هافمن را می‌سازد و کدگذاری را انجام می‌دهد.

# نحوه اجرا:
برای اجرای این کد، آن را در یک محیط ++C کپی کنید و به سادگی آن را کامپایل و اجرا کنید. کاراکترهای ورودی و فرکانس‌های مربوطه را می‌توانید تغییر دهید.

مسئله کوله پشتی چیست؟

فرض کنید که جهانگردی می خواهد کوله پشتی خود را با انتخاب حالتهای ممکن از بین وسائل گوناگونی که بیشترین راحتی را برایش فراهم می سازند پر کند. این مسئله می تواند با شماره گذاری این وسائل از ۱ تا n و تعریف برداری از متغیرهای دودویی(Binary) (j = 1,2,…n) بصورت ریاضی فرمول بندی شود. به این معنی که: اگر شیء j ام انتخاب شود در غیر اینصورت وقتی میزان راحتی باشد که وسیله j ا م فراهم می آورد و وزن آن و c اندازه کوله پشتی باشد. مسئله ما انتخاب برداری از بین بردارهای دودویی x است،که محدودیت را بر آورده کند. بطوریکه تابع هدف ماکزیمم مقدار خود را بگیرد به عنوان نمونه ای از مسائلی که می توانند بصورت مساله کوله پشتی فرمول بندی شوند، مسئله زیر را در نظر بگیرید: فرض کنید که شما مایل به سرمایه گذاری همه یا قسمتی ازسرمایه تان باشید. اگر مبلغی که برای سرمایه گذاری در نظر گرفتید c دلار باشد و n مورد برای سرمایه گذاری ممکن باشد ، اجازه دهیدکه سود حاصل از سرمایه گذاری j ام و مقدار دلارهایی باشد که آن سرمایه گذاری لازم دارد . بدین ترتیب جواب بهینه مسئله کوله پشتی که تعریف کردیم به ما این امکان را می دهدکه بهترین حالت ممکن را از بین حالتهای مختلف سرمایه گذاری انتخاب کنیم. در این رابطه باید روشی برای حل این مسئله پیدا کرد . یک روش ابتدایی که در نگاه اول توجه ما را به خود جلب می کند، عبارت از برنامه نویسی برای کامپیوتر به منظور امتحان کردن تمامی بردارهای دودویی ممکن x است، تا از بین بردارهایی که محدودیت مسئله را ارضاء می کنند بهترین را انتخاب کند.

متاسفانه تعداد چنین بردارهایی است. بطوریکه یک کامپیوتر فرضی که می تواند یک بیلیون بردار را در یک ثانیه امتحان کند؛ برای n = 60 بیش از ۳۰ سال وقت لازم دارد و بیش از ۶۰ سال برای n = 61 و دهها قرن برای n = 65 والی اخر. با این وجود، با استفاده از الگوریتمهایی خاص می توان در بسیاری موارد مسئله ای با n = 100000 را در عرض چند ثانیه روی یک کامپیوترکوچک حل کرد.

الگوریتم مرتب‌سازی، در علوم کامپیوتر و ریاضی، الگوریتمی است که لیستی از داده‌ها را به ترتیبی مشخص می‌چیند.پر استفاده‌ترین ترتیب‌ها، ترتیب‌های عددی و لغت‌نامه‌ای هستند. مرتب‌سازی کارا در بهینه سازی الگوریتم‌هایی که به لیست‌های مرتب شده نیاز دارند (مثل جستجو و ترکیب) اهمیت زیادی دارد.
مرتب‌سازی حبابی یا Bubble sort یک الگوریتم مرتب‌سازی  ساده‌است که لیست را پشت سرهم پیمایش می‌کند تا هر بار عناصر کنارهم را با هم سنجیده و اگر در جای نادرست بودند جابه‌جایشان کند. دراین الگوریتم این کار باید تا زمانی که هیچ جابه‌جایی در لیست رخ ندهد، ادامه یابد و در آن زمان لیست مرتب شده‌است. این مرتب‌سازی از آن رو حبابی نامیده می‌شود که هر عنصر با عنصر کناری خود سنجیده‌شده و درصورتی که از آن کوچک‌تر باشد جای خود را به آن می‌دهد و این کار همچنان پیش می‌رود تا کوچک‌ترین عنصر به پایین لیست برسد و دیگران نیز به ترتیب در جای خود قرار گیرند (یا به رتبه‌ای بالاتر روند یا به پایین تر لیست رانده شوند.) این عمل همانند پویش حباب به بالای مایع است.
این مرتب‌سازی از آن رو که برای کار با عناصر آن‌ها را با یکدیگر می‌سنجد، یک مرتب‌سازی سنجشی است.
با فرض داشتن n عضو در لیست، در بدترین حالت n(n − ۱) / ۲ عمل لازم خواهد بود.بدترین زمان اجرا و پیچیدگی متوسط مرتب سازی حبابی هر دو (O(n^2 می‌باشند که در آن n تعداد عناصری است که باید مرتب شوند.
الگوریتم‌های مرتب سازی بسیاری وجود دارند که بدترین زمان اجرای آنها از این بهتر است یا پیچیدگی متوسط آنها (O(n log n است. حتی بقیه اگوریتم‌های مرتب سازی از (O(n^2 مثل [مرتب سازی درجی]، عملکرد بهتری نسبت به مرتب سازی حبابی از خود نشان می‌دهند.در ادامه سورس این الگوریتم را برای ++C قرار می دهیم

تابع مرتب سازی سطلی یا صندوقی (Bucket Sort) در ++C

مرتب سازی سطلی یا مرتب سازی صندوقی ، نوعی الگوریتم مرتب سازی  است که با تقسیم کردن یک آرایه به تعدادی سطل کار می‌کند. سپس هر سطل به طور جداگانه مرتب می‌شود که این کار مرتب کردن می‌تواند از یک الگوریتم مرتب سازی دیگر استفاده کرده یا مرتب سازی سطلی را به طور بازگشتی روی آن اجرا کند. مرتب سازی سطلی تعمیم مرتب سازی لانه کبوتری است. از آن جایی که این مرتب سازی ، مرتب سازی مقایسه ای نیست ،(Ω(nlog n به عنوان حد پایین برای آن غیر قابل اجرا می‌باشد. پیچیدگی محاسباتی برای آن بر اساس تعداد سطل‌ها محاسبه می‌شود.

تابع مرتب سازی سریع (Quick Sort) در ++C

تابع مرتب سازی سریع (Quick Sort) که می توانید سورس را مشاهده کنید.

پیچیدگی زمانی اجرای الگوریتم در بهترین حالت ( Ө( n log n و در بدترین حالت ( Ө( n2 است. با استفاده محاسبات ریاضی می‌توان نشان داد در حالت متوسط نیز مرتبه اجرا ( Ө( n log n است.

 تابع مرتب سازی درجی (Insertion Sort) در ++C

مرتب‌ساز درجی (Insertion Sort) یک الگوریتم مرتب‌سازی ساده بر مبنای مقایسه است. این الگوریتم برای تعداد داده‌های زیاد، کارآمد نیست و در این موارد، الگوریتم‌های بهتری مثل مرتب‌ساز سریع، مرتب‌ساز ادغامی و مرتب‌ساز پشته وجود دارد.

این الگوریتم به این صورت عمل می‌کند که تمام عناصر لیست را یکی یکی برمی‌دارد و آن را در موقعیت مناسب در بخش مرتب شده قرار می‌دهد. انتخاب عنصر مورد نظر، اختیاری است و می‌تواند توسط هر الگوریتم انتخابی، انتخاب شود. مرتب‌سازی درجی به صورت درجا عمل می‌کند. نتیجه عمل بعد از k مرحله، حاوی k عنصر انتخاب شده به صورت مرتب شده است.

بهترین حالت زمانی است که آرایه از قبل مرتب شده باشد. در این حالت زمان اجرای الگوریتم از (O(n است: در هر مرحله اولین عنصر باقیمانده از لیست اولیه فقط با آخرین عنصر لیست مرتب شده مقایسه می‌شود. این حالت بدترین حالت برای مرتب‌ساز سریع (غیرتصادفی و با پیاده‌سازی ضعیف) است که زمان (O(n^۲ صرف می‌کند. بدترین حالت این الگوریتم، زمانی است که آرایه به صورت معکوس مرتب شده باشد. در این حالت هر اجرای حلقه داخلی، مجبور است که تمام بخش مرتب شده را بررسی کرده و انتقال دهد. در این زمان اجرای الگوریتم، مثل حالت متوسط، دارای زمان اجرای (O(n^۲ است که باعث می‌شود استفاده از این الگوریتم برای مرتب‌سازی تعداد داده‌های زیاد، غیرعملی شود. گرچه حلقه داخلی مرتب‌ساز درجی، خیلی سریع است و این الگوریتم را به یکی از سریع‌ترین الگوریتم‌های مرتب‌سازی، برای تعداد داده‌های کم (معمولاً کمتر از ۱۰)، تبدیل می‌کند.

الگوریتم مرتب سازی ادغامی (Merge Sort) در ++C

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

ویژگی‌های مرتب‌سازی ادغامی

1- پیچیدگی زمانی اجرای الگوریتم در تمامی حالات ( Ө( n log n است. چرا که این الگوریتم تحت هر شرایطی آرایه را به دو قسمت کرده و مرتب‌سازی را انجام می‌دهد.

2- پیچیدگی حافظه مصرفی بستگی به روش پیاده‌سازی مرحله ادغام دارد، که تا ( O( n افزایش می‌یابد. پیاده‌سازی درجای این الگوریتم حافظه مصرفی مرتبه ( Ө( 1 دارد. اما اجرای آن در بدترین حالت زمانبر است.

3- الگوربتم مرتب‌سازی ادغامی با پیاده‌سازی فوق یک روش پایدار است. چنین الگوریتمی ترتیب عناصر با مقدار یکسان را پس از مرتب‌سازی حفظ می‌کند.

تابع مرتب سازی انتخابی(Selection Sort) در ++C

مرتب‌سازی انتخابی یکی از انواع الگوریتم مرتب‌سازی می‌باشد که جزو دستهٔ الگوریتمهای مرتب‌سازی مبتنی بر مقایسه‌است.این الگوریتم دارای پیچیدگی زمانی از درجهٔ (O(n ² است که به همین دلیل اعمال آن روی مجموعهٔ بزرگی از اعداد کارا به نظرنمی رسد و به طور عمومی ضعیفتر از نوع مشابهش که مرتب‌ساز درجی است عمل می‌کند.این مرتب سازی به دلیل سادگی اش قابل توجه‌است.

ویژگی‌های مرتب‌سازی انتخابی

1-با توجه به قطعه کد نوشته شده، ترتیب عناصر تغییری در عملکرد آن اینجا نمی‌کند. یعنی این الگوریتم برای داده‌های کاملا مرتب، نامرتب تصادفی و مرتب معکوس به یک ترتیب عمل کرده و تمام مقایسه‌های محاسبه شده در رابطه فوق را انجام می‌دهد. بنابراین پیچیدگی این الگوریتم در بهترین حالت و حالت منوسط نیز ( Θ( n ² است.

2- مرتب‌سازی انتخابی یک روش مرتب‌سازی درجا است. یعنی عملیات مرتب‌سازی به در داخل خود لیست و بدون نیاز به حافظه کمکی بزرگ انجام می‌گیرد.

3- در پیاده‌سازی مرتب‌سازی انتخابی به روش فوق، اگر دو عنصر با مقدار بیشینه داشته باشیم، اولی انتخاب شده و به انتهای لیست منتقل می‌شود. در نتیجه ترتیب آنها به هم می‌خورد. بنابراین این پیاده‌سازی روش پایدار نیست. در روش پایدار ترتیب عناصر با مقدار یکسان تغییر نمی‌کند. اما اگر در مقایسه عناصر آرایه به جای > از => استفاده کنید، مرتب‌سازی پایدار خواهد شد.

• دانلود از سرور Trainbit

• دانلود از سرور Pico File

ماتریس بالا مثلثی:
ماتریسی که تمام اعداد پایین قطر اصلی آن 0 باشند ، ماتریس بالا مثلثی نام دارد.
به بیان دیگر می توان گفت ، در ماتریس های بالا مثلثی ، رابطه زیر برقرار است:

If  J>I => X[I,J]=0

این سورس بالا و پایین مثلثی ماتریس را بدست آورده و چاپ می کند و به زبان ++C نوشته شده است .

 

مرتب‌سازی شِل یا مرتب سازی صدفی یکی از قدیمی‌ترین الگوریتم‌های مرتب‌سازی و تعمیمی از مرتب‌سازی درجی با در نظر گرفتن دو نکته زیر است:

• الگوریتم مرتب‌سازی درجی درصورتی کارآمد است که داده‌ها تقریباً مرتب باشند.
• مرتب‌سازی درجی معمولاً کم بازده‌است چون مقادیر را در هر زمان فقط به اندازه یک موقعیت جابجا می‌کند.

یک الگوریتم مرتب سازی زمان مرتب سازی خوبی دارا است لذا سرعت عمل روش مرتب سازی شل از روش‌های انتخابی، درجی و حبابی بیشتر است.

در روش مرتب‌سازی درجی در بدترین حالت الگوریتم از (O(n ۲ است در حالی که با مرتب‌سازی صدفی این زمان به (O(n log۲ کاهش یافته‌ است.

در مرتب‌سازی صدفی یا شِل، ابتدا داده‌ها در گام‌های بزرگتری جابه جا می‌شوند اما در هر مرحله فاصله این جابه جایی‌ها کم تر شده و به جابه جایی‌های جزئی می‌رسد.

بطور مثال :

مرتب سازی شل در C
این سورس به زبان C می باشد که چند عدد به صورت دستی و انتخابی داده شده که آنها را با روش Shell sort مرتب می کند.

# توضیحات:
- shellSort: تابعی است که الگوریتم Shell Sort را پیاده‌سازی می‌کند.
- printArray: برای چاپ آرایه‌ای که مرتب شده استفاده می‌شود.
- در main: یک آرایه تعریف شده و پس از مرتب‌سازی، آرایه مرتب‌شده چاپ می‌شود.

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

مرتب سازی شل در ++C
به این سورس 5 عدد به صورت دستی و انتخابی داده شده و آنها را با روش Shell sort مرتب می کند و در نهایت آرایه ای قبل و بعد از مرتب شدن چاپ می کند.

خروجی قطعه کد بالا در ادامه آمده است.

 :Array before sorting
12 34 54 2 3
 :Array after sorting
2 3 12 34 54