تعداد حالات ممکن خرد کردن 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 یا هر عددی کن

Coins.rar

موفق باشید

[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]

من یه برنامه که مقسوم علیه های یک عدد را محاسبه میکنه نوشتم که می تونی از همین روش برای این مسئله استفاده کنی
https://barnamenevis.org/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;

}