چند تا سوال در c++ لطفا کمک کنید............

[xman_dj]

سلام
اگه راهنماییم کنید لطف بزرگی کردین
1-اونایی که با مرتب سازی حبابی آشنان(مرتب میکند آرایه رو به این صورت که عنصر بزرگ به راست میره)
چطور میشه بعد مرتب سازی دیگه از تکرار بیش از اندازه جلوگیری کنه.........یعنی دیگه برنامه ادامه نده به کارش؟
2-میخواست کاری کنم که تو برنامه (با تابع نوشته شه)تو قسمت ورودی(cin)نگذاره کاراکتر چاپ شه از چاپش جلوگیری کنه.....................و برعکس این عمل(یعنی فقط کاراکتر چاپ شه از نوشتن عدد جلوگیری کنه)
3-برنامه ای که اسامی رو گرفته از ورودی در آرایه گذاشته و براساس الفبای انگلیسی مرتب کرده و خروجی دهد...............بعد از کاربر یه اسم بخواد و در آرایه جستجو کنه که هست یا نه؟(در واقع search کنه با تابع strcmp در string.h فکر کنم این عمل انجام می شه)
البته در زبان c++
با تشکر فراوان..........

[emad_67]

چطور میشه بعد مرتب سازی دیگه از تکرار بیش از اندازه جلوگیری کنه.........یعنی دیگه برنامه ادامه نده به کارش؟فقط کافیه یه مقدار flag رو در حلقه اصلی در نظر بگیری به این شکل:


bool flag=1;
for(int i=0;i<10 && flag;i++)
{
flag=0;
for(int j=0;j<10;j++)
{
if(s[j]>s[j+1])
{
flag=1;
//some code
}
}
}
در واقع وقتی شرط if برقرار میشه یعنی یه مقداری وجود داره که باید مرتب بشه، پس flag رو برابر 1 قرار میدیم تا حلقه ادامه پیدا کنه.

-میخواست کاری کنم که تو برنامه (با تابع نوشته شه)تو قسمت ورودی(cin)نگذاره کاراکتر چاپ شه از چاپش جلوگیری کنه.....................و برعکس این عمل(یعنی فقط کاراکتر چاپ شه از نوشتن عدد جلوگیری کنه)منظورات اینه که مثلا طرف نتونه حرف تایپ کنه و فقط عدد بنویسه؟
این برنامه الان فقط عدد میگیره:


void main()
{
char s;
do
{
s=getch();
if(s>='0' && s<='9')
cout<<s<<flush;
}
while(s!=13);
}
و تا وقتی که enter نزنی ادامه پیدا میکنه.

برنامه ای که اسامی رو گرفته از ورودی در آرایه گذاشته و براساس الفبای انگلیسی مرتب کرده و خروجی دهد...............بعد از کاربر یه اسم بخواد و در آرایه جستجو کنه که هست یا نه؟(در واقع search کنه با تابع strcmp در string.h فکر کنم این عمل انجام می شه)
البته در زبان c++در این مورد هم که خودت گفتی دیگه. ابتدا یه آرایه کاراکتری از نوع اشاره گر تعریف کن و بعد با strvmp مقایسه کن. مثل همین bubble sort رو میتونی روی رشته ها پیاده کنی.
ضمنا بهتره که هر سوالت رو توی یه تاپیک بپرسی

[Alireza Orumand]

چطور میشه بعد مرتب سازی دیگه از تکرار بیش از اندازه جلوگیری کنه.........یعنی دیگه برنامه ادامه نده به کارش؟

تو این الگوریتم تو هر مرحله اجرا فقط یکی از عناصر آرایه به جای درست انتقال پیدا میکنن. و در مرحله بعد اون اعداد دیگه بررسی نمیشن و فقط اعدادی که مرتب نشده هستن بررسی میشن.
مثلا اعداد زیر رو در نظر بگیرید:
9و7و5و1و2و3و4
بعد از اولین اجرا به شکل زیر مرتب میشه:
7و 5 و 1 و 2 و 3 و 4 و 9
در مرحله بعد عدد 9 که در جای صحیح خودش قرار گرفته دیگه اصلا جزئ محاسبات نمیاد.
5 و 1 و 2 و 3 و 4 و 7 و 9
پس همونطور که میبینید اعدادی که مرتب میشن دیگه جزئ محاسبات نیست. ولی در بعضی حالات قبل از اینکه کلیه ی مراحل انجام بشه دیگه آرایه ی ما مرتب میشه و نیازی نیست که برنامه ادامه پیدا کنه. در چینن مواردی راه حل رو دوستمون گفتن فقط یه اشکال کوچولو وجود داره و اون اینکه شرط رو باید بیرون حلقه داخلی چک بشه نه داخل یعنی اینکه شما آرایه زیر رو در نظر بگیر:
1 و 2 و 3 و 5 و 4 و 6
طبق فرموده دوستمون در همون بار اول اجرا چون نیازی به جابجایی بین 1 و 2 نیست فلگی که گفتن به 0 ست شده و برنامه تموم میشه.
راه بهتر اینه که شما یه شمارنده تو حلقه داخلی قرار بدی و بعد از هر بار جابجایی به مقدار اون یکی اضافه کنید. حالا بعد از اجرای حلقه داخلی اگر مقدار شمارنده صفر بود یعنی هیچ عددی برای جابجایی وجود نداشت میتونی به ادامه برنامه خاتمه بدی.


void bubble_sort ( int arr [ ] , int n )
{
int temp , counter ;
for (int i = n - 2 ; i >= 0 ; i -- )
{
counter = 0 ;
for ( int j = 0 ; j <= i ; j ++ )
{
if ( arr [ j ] > arr [ j + 1 ] )
{
temp = arr [ j ] ;
arr [ j ] = arr [ j + 1 ] ;
arr [ j + 1 ] = temp;
counter ++ ;
}
}
if ( c == 0 )
break ;
}
}


موفق باشید.

[emad_67]

در مرحله بعد عدد 9 که در جای صحیح خودش قرار گرفته دیگه اصلا جزئ محاسبات نمیاد.توی bubble sort معمولا به این شکل عمل نمیشه. البته میشه اینجوری پیاده سازی کرد.

در چینن مواردی راه حل رو دوستمون گفتن فقط یه اشکال کوچولو وجود داره و اون اینکه شرط رو باید بیرون حلقه داخلی چک بشهروشی که من نوشتم درست هست. ببینید. مثلا وقتی داریم:


1 2 6 5 3
در ابتدا که flag=1 هست و کنترل برنامه به حلقه for درونی میرسه. در این حلقه کل حلقه به صورت کامل طی میشه یعنی عبارت حاصل در اولین اجرای for داخلی میشه:


1 2 5 3 6
یعنی در لحظه ای که جای 5 و 6 عوض میشه مقدار flag هم برابر 1 میشه و وقتی که حلقه for درونی تموم بشه مقدار flag در حلقه بیرونی چک میشه و چون 1 هست برنامه ادامه پیدا میکنه.

راه بهتر اینه که شما یه شمارنده تو حلقه داخلی قرار بدی و بعد از هر بار جابجایی به مقدار اون یکی اضافه کنید. حالا بعد از اجرای حلقه داخلی اگر مقدار شمارنده صفر بود یعنی هیچ عددی برای جابجایی وجود نداشت میتونی به ادامه برنامه خاتمه بدی.
برنامه منم دقیقا همین کا رو میکنه دیگه ولی با true و false کردن flag.

[Alireza Orumand]

عماد جان فرمایش شما در مورد flag درسته. من شرط flagرو که تو حلقه اول تست میشد ندیدم. از این بابت عذر خواهی میکنم.
ولی شرط حلقه دوم همیشه به تعدادی حلقه بیرونی وابسته هست یعنی با هر بار اجرای حلقه بیرونی باید از تعداد اجراهای حلقه درونی کاسته بشه اگر این تغییر تو برنامه شما لحاظ بشه فرمایش شما کاملا صحیح و برنامه ها مثل هم هستن.
موفق باشید.

[emad_67]

یعنی با هر بار اجرای حلقه بیرونی باید از تعداد اجراهای حلقه درونی کاسته بشه
در این مورد هم همون طور گفتم معمولا برای bubble sort به این صورت عمل نمیشه و اجازه میدن تا حلقه داخلی تا آخر بره.
درسته تفاوت برنامه من و شما در همینه

[Alireza Orumand]

در این مورد هم همون طور گفتم معمولا برای bubble sort به این صورت عمل نمیشه و اجازه میدن تا حلقه داخلی تا آخر بره.
خیر اینطور نیست. با هر بار اجرا یکی از عناصر مرتب میشه و دیگه نیازی به بررسی اون عضو نیست. حد اقل تا وقتی ما درس میخوندیم درباره این الگوریتم این اتفاق نمیافتاد و بیهنه بودن الگوریتم اینقدر اهمیت داشت که عناصر مرتب شده مجدد بررسی نشن.
شما این کار رو بکن. فرض کن یه آرایه داری با یک میلیون عضو و میخواهی به این روش مرتب کنی. محاسبه کنید ببینید چه سرباری به سیستم تحمیل میکنید.
درباره این که فرموده بودید درمورد bubble sort معمولا اجازه میدن حلقه داخلی همیشه کامل اجرا بشه، والا من تو این چند سالی که درس خوندم و کار کردم کسی رو ندیدم حلقه داخلی رو همیشه ادامه بده. میشه بفرمایید طبق کدوم منبع شما میفرمایید معمولا یا چند نفر رو میشناسید که این کار رو بکنن؟ آخه وقتی میگیم معمولا منظورمون بالای 70-80% هست.

[emad_67]

وقتی بحث بهینه بودن پیش بیاد حرف شما درسته ولی در حالت عادی حلقه رو تا آخر ادامه میدن به همین دلیل هم هست که میگن پیچیدگی اون O(n^2) است. ولی خوب اگه بخوایم بهینش کنیم قضیه فرق میکنه. من از کتاب دیتیل این مثال رو خوندم و توی اون هم تا آخر حلقه رو جلو برده بود. (بحث بهینه بودن مطرح نبود).
توی سایت ها هر دو مدلش هست. مثلا :
http://mathbits.com/mathbits/compsci/Arrays/Bubble.htm
http://www.cprogramming.com/tutorial/computersciencetheory/sorting1.html
http://en.wikipedia.org/wiki/Bubble_sort

[Alireza Orumand]

تنها زمانی بین یک کد بهینه و غیر بهینه شده تفاوت میشه گذاشت که بهینه کردن برنامه هزینه بر باشه جایی که بهینه بودن یه الگوریتم نسبت به غیر بهینه بودنش هیچ هزینه ای نداره روش غیر بهینه میشه روش غلط.
موفق باشید.