تعداد حالات ممکن خرد کردن 5000 تومانی با اسکناس های 10و20و50و100و200و500و1000و2000 تومانی از دوستان عزیز میخوام که یه راهنمایی به من بکنن در مورد الگوریتم این مسله
مننونم
تعداد حالات ممکن خرد کردن 5000 تومانی با اسکناس های 10و20و50و100و200و500و1000و2000 تومانی از دوستان عزیز میخوام که یه راهنمایی به من بکنن در مورد الگوریتم این مسله
مننونم
خوب می تونید 5000 رو به همین اسکناس هایی که گفتید تقسیم کنید، مثلاً 5000/10 میشه 500. این یک حالت! بعد مساله رو بسط بدین به اسکناس های بعدی و حالت هارو باهم ترکیب کنید؛ مثلاً 250 تا 10 تومانی و 125 تا 20 تومانی، این هم یک حالت! بایستی برنامه شما یه جورایی حالت تودرتو داشته باشه.
از حلقه های تو در تو استفاده کن ! بعد کنتور حلقه ها رو با هم جمع بزن ...
از شما دوستان عزیز ممنون ولی من خودم اینایی که گفتید میدونم مشکل من سر همون چگونگی تودر تویی مسله هستش اگه میشه یه الگوریتم پیشنهاد بدید مرسی
دوست عزیز
سلام
اگر فقط به دنبال تعداد جوابها هستید که با استفاده از معادله سیاله حل میشه( به کتابهای ساختمان گسسته و جبر و احتمال مراجعه کنید )
من هم سعی میکنم بزودی برنامه اش رو براتون بنویسم
موفق باشید
سلام
من برنامه رو براتون نوشتم ، البته خیلی تند تند ، فکر می کنم درست کارکنه . از راه حل بازگشتی استفاده کردم. البته خیلی میشه از این بهینه تر نوشت که امیدوارم شما براش وقت بزارید و درستش کنید.
راهنمایی واسه یک قسمت از بهینه سازی : روی 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 یا هر عددی کن
Coins.rar
موفق باشید
اما ما در نوشتن این برنامه فقط اجازه داریم از حلقه های تودر تو استفاده کنیم مشخصاً for البته من خودم به یه جاهایی رسیدم که باید 8 تا for تو در تو بنویسم بعد روی تعداد انجامشون کار کنم اما همچنان تو کفم در ضمن نمیشه از فرمول های ریاضی جبر و احتمال استفاده کرد چون او ن ها یک خطی اند
و نکته دیگه اینکه ++C باشه
سلام
تعداد سکه ها معلومه یا ممکنه تغییر کنه؟ ( الان این برنامه رو من با این فرض نوشتم که تعداد سکه ها معلوم نیست )
ضمنا این کد رو طوری نوشتم که تقریبا 90% با C++ یکی باشه و بقیه رو هم راحت میشه تبدیل کرد.
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
این حالت کلی چیزیه که می خواستین من همینجا تایپش کردم بهتر از این نشد کمی سعی کنید حلش سادس
سلام
فکر می کنم مدل 8 تا حلقه تو در تو بتونه به دوستمون کمک کنه ( به شرطی که تعداد انواع سکه ها ثابت باشه )
موفق باشید
از لطفت خیلی ممنون ولی اگه میشه یه کمک دیگه به من بکنید این برنامه مشکلش چیه؟
#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();
}
اگه بخوای از 8 ات حلقه استفاده کنی سرعت برنامت میاد پایین
داینامیکی حلش کن
یعنی 1 آرایه ی بزرگ تعریف کن بعد تعداد حالات هر کدومو از روی قبیلیش به دست بیار
مثال:
اول همه ی آرایتو 1 بکن
تعداد حالات برای 500=تعداد حالات برای 450+تعداد حالات برای 50
+تعداد حالات برای 400+تعداد حالات برای 100
....
اگه متوجه نشدی کدشو بهت بدم
آخرین ویرایش به وسیله mozdour : جمعه 18 خرداد 1386 در 17:02 عصر دلیل: اشکال در الگوریتم متن قبل
اگه لطف کنی وکدش رو بدی خیلی خیلی ممنون میشم
#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;
}
اگه الگوریتم رو نفهمیدی بیشتر توضیح بدم
من یه برنامه که مقسوم علیه های یک عدد را محاسبه میکنه نوشتم که می تونی از همین روش برای این مسئله استفاده کنی
https://barnamenevis.org/showthread.php?t=66600
سلام
من این کد رو البته به زبان 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;
}
}
}
}
}
}
سلام
این کد مشکلت را حل میکنه.
#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;
}