Помощ с алгоритъм за една интересна задачка.


3

Да се напише програма за изчисляване броя на различните начини на разкрояване на 100-метрова връв на парчета по 2,5,20 и 50 метра.

Трябва да напиша тази задачка на C++ , но за съжаление не мога да се сетя начина. 
Може ли малко помощ ? 




Отговори



1

Здрасти, ТУК разглеждат подобен проблем. Обяснението е прилично и би трябвало да ти свърши работа.


от sgkazakov (288 точки)


0

Аз малко набързо успях да скалъпя това:

using System;

namespace DivideRope
{
    class Program
    {
        static void Main()
        {
            int sumOfFifty = 0;
            int sumOfTwenty = 0;
            int sumOfFive = 0;
            int SumOfTwo = 0;
            int sum;

            for (int countFifty = 0; countFifty <= 100/50; countFifty++)
            {
                sumOfFifty = countFifty * 50;
                for (int countTwenty = 0; countTwenty <= 100/20; countTwenty++)
                {
                    sumOfTwenty = countTwenty * 20;
                    for (int countFive = 0; countFive <= 100/5; countFive++)
                    {
                        sumOfFive = countFive * 5;
                        for (int countTwo = 0; countTwo <= 100/2; countTwo++)
                        {
                            SumOfTwo = countTwo * 2;
                            sum = sumOfFifty + sumOfTwenty + sumOfFive + SumOfTwo;
                            if (sum == 100)
                            {
                                Console.WriteLine("{0,2} * 50 + {1,2} * 20 + {2,2} * 5 + {3,2}* 2",countFifty, countTwenty, countFive, countTwo);
                            }

                        }
                    }
                }
            }
            Console.ReadLine();
        }
    }
}

Ама знам, че има и по-интелигентен начин. Този е доста дърварски.


от vladko_sz (195 точки)


2

Здравей, това е много готина задачка от темата за рекурсия. На мен лично в началото ми беше доста трудно да я схвана дори като понятие, но после посвикнах разбрах я и вече почти нямам проблеми с нея. Според мен нищо не пречи задачата да се реши и с променлив брой парчета, т.е. да не са 4 (2,5,20,50), а да си въвеждаш броя и съответно самите числа.

Щях да пиша програмата на C#, но забелязах че ти трябва на C++. Ето една реализация на рекурсивната програма:

#include <iostream>
using namespace std;

const int M=100; //дължина на оградата
int s=0; //брой начини
int n; //брой на различните по дължина парчета - в случая са 4 (2,5,20,50)

void Solve(int a[16],int b[16],int x,int t)
{
    if (x==0)
    {
        s++;
        cout<<M<<" = "<<a[0]<<" * "<<b[0];
        for (int i=1;i<n;i++)
        {
             cout<<" + "<<a[i]<<" * "<<b[i];
        }
        cout<<endl;
        return;
    }
    for (int i=0;i<n;i++)
    {
        if (x-a[i]>=0 and t>=a[i])
        {
            b[i]++;
            Solve(a,b,x-a[i],a[i]);
            b[i]--;
        }
    }
}

int main ()
{
    int a[16],b[16];
    cin>>n;
    for (int i=0;i<n;i++)
    {
        cin>>a[i];
        b[i]=0;
    }
    Solve(a,b,100,100);
    cout<<s<<endl;
    return 0;
}

Според мен това би било подобаващо решение на задачата. Ако имаш Програмиране = ++ Алгоритми виж обясненията в Глава 1 - Въведение в Алгоритмите или по-точно 1.3.4. Разбиване на числа.

 

от dobi.6 (10 точки)