تعداد حالات ممکن خرد کردن 5000 تومانی

[Ehsan_EHMO]

تعداد حالات ممکن خرد کردن 5000 تومانی با اسکناس های 10و20و50و100و200و500و1000و2000 تومانی از دوستان عزیز میخوام که یه راهنمایی به من بکنن در مورد الگوریتم این مسله
مننونم

[amir_cpp]

خوب می تونید 5000 رو به همین اسکناس هایی که گفتید تقسیم کنید، مثلاً 5000/10 میشه 500. این یک حالت! بعد مساله رو بسط بدین به اسکناس های بعدی و حالت هارو باهم ترکیب کنید؛ مثلاً 250 تا 10 تومانی و 125 تا 20 تومانی، این هم یک حالت! بایستی برنامه شما یه جورایی حالت تودرتو داشته باشه.

[mehrzad007]

از حلقه های تو در تو استفاده کن ! بعد کنتور حلقه ها رو با هم جمع بزن ...

[Ehsan_EHMO]

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

[azmoodeh]

دوست عزیز

سلام

اگر فقط به دنبال تعداد جوابها هستید که با استفاده از معادله سیاله حل میشه( به کتابهای ساختمان گسسته و جبر و احتمال مراجعه کنید )


من هم سعی میکنم بزودی برنامه اش رو براتون بنویسم

موفق باشید

[azmoodeh]

سلام

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

راهنمایی واسه یک قسمت از بهینه سازی : روی TheNumber توی حلقه ها فکر کن :گیج:



public partial class Form1 : Form
{
int CoinCount;
long TheNumber;


private ArrayList Coin = new ArrayList();
private ArrayList States = new ArrayList();



public Form1()
{
InitializeComponent();
}
private void Form1_Load(object sender, EventArgs e)
{

}

private void button1_Click(object sender, EventArgs e)
{
Coin.Clear();
Coin.Add(1);
Coin.Add(2);
Coin.Add(5);
Coin.Add(10);
Coin.Add(25);
Coin.Add(50);

TheNumber = 10;

CoinCount = Coin.Count;
ArrayList _list=new ArrayList();
for (int i = 0; i < CoinCount; i++) {
_list.Add(0);
}
CountState(ref _list, CoinCount);

}

void CountState(ref ArrayList _List, int _Order)
{
if (_Order == 0) {
return;
}
for (int i = 0; i <= TheNumber; i++) {
_List[_Order-1] = i;
if(IsAnswer(_List)){
PrintList(_List);
}
CountState(ref _List, _Order - 1);

}

}

bool IsAnswer(ArrayList _List) {
double temp=0;
for (int i = 0; i < _List.Count; i++)
{
temp += (int)_List[i] * (int)Coin[i];
}
if (temp == TheNumber) {
return true;
}

return false;
}
void PrintList(ArrayList _List) {
string s;
s = "(";

for (int i = 0; i < _List.Count-1; i++) {

s =s+_List[i].ToString () + ",";
}
s = s + _List[_List.Count - 1].ToString() + ") \v ";
textBox1.Text = textBox1.Text+s;
this.Refresh();
}

}


من برنامه رو برای 10 نوشتم حالا شما TheNumber رو 5000 یا هر عددی کن

8925

موفق باشید

[Ehsan_EHMO]

اما ما در نوشتن این برنامه فقط اجازه داریم از حلقه های تودر تو استفاده کنیم مشخصاً for البته من خودم به یه جاهایی رسیدم که باید 8 تا for تو در تو بنویسم بعد روی تعداد انجامشون کار کنم اما همچنان تو کفم:گریه: :افسرده: در ضمن نمیشه از فرمول های ریاضی جبر و احتمال استفاده کرد چون او ن ها یک خطی اند
و نکته دیگه اینکه ++C باشه

[azmoodeh]

سلام

تعداد سکه ها معلومه یا ممکنه تغییر کنه؟ ( الان این برنامه رو من با این فرض نوشتم که تعداد سکه ها معلوم نیست )

ضمنا این کد رو طوری نوشتم که تقریبا 90% با C++ یکی باشه و بقیه رو هم راحت میشه تبدیل کرد.

[mehrzad007]

for i1=1 to 5000 step 10
for i2=1 to 5000 step 20
....
for i8=1 to 5000 step 1000
if i1+i2+...+i8=5000 then print i1-i2-..-i8
next i8
...
next i1

[mehrzad007]

این حالت کلی چیزیه که می خواستین من همینجا تایپش کردم بهتر از این نشد کمی سعی کنید حلش سادس

[azmoodeh]

سلام

فکر می کنم مدل 8 تا حلقه تو در تو بتونه به دوستمون کمک کنه ( به شرطی که تعداد انواع سکه ها ثابت باشه )


موفق باشید

[Ehsan_EHMO]

از لطفت خیلی ممنون ولی اگه میشه یه کمک دیگه به من بکنید این برنامه مشکلش چیه؟
#include<iostream.h>
#include<conio.h>
main()
{
int a,b,c,d,e,f,g,h,count=0;
for(a=1;a>501;a++)
for(b=1;b>251;b++)
for(c=1;c>101;c++)
for(d=1;d>51;d++)
for(e=1;e>26;e++)
for(f=1;f>11;f++)
for(g=1;g>6;g++)
for(h=1;h>3;h++)
if(h*2000+g*1000+f*500+e*200+d*100+c*50+b*20+a*10= =5000)
count=count+1;
cout<<"result is ::"<<count;
getch();
}

[mozdour]

اگه بخوای از 8 ات حلقه استفاده کنی سرعت برنامت میاد پایین
داینامیکی حلش کن
یعنی 1 آرایه ی بزرگ تعریف کن بعد تعداد حالات هر کدومو از روی قبیلیش به دست بیار
مثال:
اول همه ی آرایتو 1 بکن
تعداد حالات برای 500=تعداد حالات برای 450+تعداد حالات برای 50
+تعداد حالات برای 400+تعداد حالات برای 100
....
اگه متوجه نشدی کدشو بهت بدم

[Ehsan_EHMO]

اگه لطف کنی وکدش رو بدی خیلی خیلی ممنون میشم

[mozdour]

#include <iostream>
using namespace std;
int coin[8] = {10,20,50,100,200,500,1000,2000};
long long dyn[5001];
int main ()
{
for (int i = 0; i <= 5001; i++)
dyn[i] = 1;

for (int i = 1; i < 8; i++)
for (int j = coin[i]; j <= 5001; j++)
dyn[j] += dyn[j - coin[i]];
int n=1;
while(cin >> n)
{
if(dyn[n]==1)
cout << "There is only 1 way to produce " << n << " cents change." << endl;
else
cout << "There are " << dyn[n] << " ways to produce " << n << " cents change." << endl;
}
return 0;
}

اگه الگوریتم رو نفهمیدی بیشتر توضیح بدم

[pluskid]

من یه برنامه که مقسوم علیه های یک عدد را محاسبه میکنه نوشتم که می تونی از همین روش برای این مسئله استفاده کنی
http://barnamenevis.org/forum/showthread.php?t=66600

[Musician]

سلام
من این کد رو البته به زبان PHP نوشتم که این کار رو با سکه های 50، 25، 10، 5 و 1 سنتی انجام میده. کارش رو درست انجام میده ولی برای n های بزرگتر از 1000 خیلی سرعتش میاد پایین.

$resnum=0;
$ta=(int)($n/50);
for($a=0; $a<=$ta; $a++){
$q=$a*50;
if($q>$n) break;
$m1=$n-$q;
$tb=(int)($m1/25);
for($b=0; $b<=$tb; $b++){
$q=$b*25;
if($q>$m1) break;
$m2=$m1-$q;
$tc=(int)($m2/10);
for($c=0; $c<=$tc; $c++){
$q=$c*10;
if($q>$m2) break;
$m3=$m2-$q;
$td=(int)($m3/5);
for($d=0; $d<=$td; $d++){
$q=$d*5;
if($q>$m3) break;
$m4=$m3-$q;
$te=$m4;
for($e=0; $e<=$te; $e++){
$q=$e;
$m5=$m4-$q;
if($m5==0){
$resnum++;
break;
}
}
}
}
}
}

[tdkhakpur]

سلام
این کد مشکلت را حل میکنه.


#include <iostream.h>
#include <conio.h>
#include <stdio.h>
int array[500], c=0;
void calculate(int rial, int item, int c)
{
if((rial-item)>0 ){
array[c] = item;
if( (rial-2000)>0 )
calculate(rial-2000, 2000, c+1);
if( (rial-1000)>0 )
calculate(rial-1000, 1000, c+1);
if( (rial-500)>0 )
calculate(rial-500, 500, c+1);
if( (rial-200)>0 )
calculate(rial-200, 200, c+1);
if( (rial-100)>0 )
calculate(rial-100, 100, c+1);
if( (rial-50)>0 )
calculate(rial-50, 50, c+1);
if( (rial-20)>0 )
calculate(rial-20, 20, c+1);
if( (rial-10)>0 )
calculate(rial-10, 10, c+1);
}else{
cout<<"\n{";
for( int i=0; i<c; i++ )
cout << array[i] << ",";
cout<<"}";
getch();
}
}
int main()
{
clrscr();
calculate(5000, 5, 0);
getch();
return 0;
}