Форум программистов, компьютерный форум CyberForum.ru

Определить число безопасных стопок - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.56
firefox123
0 / 0 / 0
Регистрация: 17.11.2013
Сообщений: 39
15.12.2013, 12:03     Определить число безопасных стопок #1
При переработке радиоактивных материалов образуются отходы трех видов — особо опасные (тип http://www.cyberforum.ru/cgi-bin/latex.cgi?A), неопасные (тип http://www.cyberforum.ru/cgi-bin/latex.cgi?B) и совсем не опасные (тип http://www.cyberforum.ru/cgi-bin/latex.cgi?C). Для их хранения используются одинаковые контейнеры. После помещения отходов в контейнеры последние укладываются вертикальной стопкой. Стопка считается взрывоопасной, если в ней подряд идет более одного контейнера типа http://www.cyberforum.ru/cgi-bin/latex.cgi?A. Стопка считается безопасной, если она не является взрывоопасной. Для заданного количества контейнеров http://www.cyberforum.ru/cgi-bin/latex.cgi?N определить число безопасных стопок.

Формат входных данных
Одно число http://www.cyberforum.ru/cgi-bin/latex.cgi?1 < N < 20

Формат выходных данных
Одно число — количество безопасных вариантов формирования стопки.

Подскажите, как решить? Если бы не было стопок http://www.cyberforum.ru/cgi-bin/latex.cgi?C, то ответом было бы http://www.cyberforum.ru/cgi-bin/latex.cgi?N + 1 число Фибоначчи.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.12.2013, 12:03     Определить число безопасных стопок
Посмотрите здесь:

C++ Дано натуральное число n, символы s1...,sn. Определить число вхождений в последовательность s1...,sn группы букв abc, aba.
Дано натуральное число n (n>99). Определить число сотен внем C++
C++ Определить, сколько пар (положительное число, отрицательное число) находятся в начале массива
C++ Дано натуральное четырехзначное число n. Определить, является ли это число перевертышем
C++ Методом обхода в глубину определить число компонент связности и цикломатическое число графа
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
vndtta
66 / 43 / 5
Регистрация: 17.10.2011
Сообщений: 146
Завершенные тесты: 1
15.12.2013, 12:54     Определить число безопасных стопок #2
пусть n=a+b+c

сначала разместим контейнеры типа А, между ними должен быть прмежуток хотябы 1 контенер другого типа - значит А контейнеров можно разместить по n-(a-1) позициям ( n - количество позиций в безопасной стопке, a - кол-во контейнеров типа А, (a-1) - количество промежутков между контейнерами типа А)

Chttp://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{matrix}a\\ n-a+1 \end{matrix}=(n-a+1)!/(a!(n-a)!)=(n-a+1)!/(a!(b+c)!)

после размещений а контейнеров останется n-a=b+c позиций, теперь разместим b контейнеров типа B по этим позициям( на самом деле B или С не играет роли, одинаковое число получится)

Chttp://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{matrix}b\\ b+c \end{matrix}=(b+c)!/(b!(b+c-b)!)=(b+c)!/(b!c!)

перемножим и получим окончательный ответ

(n-a+1)!/(a!b!c!)

в данном случае у нас все контейнеры одного типа одинаковые - поэтому использованы сочетания (http://ru.wikipedia.org/wiki/%D0%A1%...BD%D0%B8%D0%B5)
если бы контейнеры были пронумерованы, тогда имел бы значение их порядок и мы использовали бы размещения(http://ru.wikipedia.org/wiki/%D0%A0%...BD%D0%B8%D0%B5)
firefox123
0 / 0 / 0
Регистрация: 17.11.2013
Сообщений: 39
15.12.2013, 13:15  [ТС]     Определить число безопасных стопок #3
vndtta, но a, b, c не даны ведь
vndtta
66 / 43 / 5
Регистрация: 17.10.2011
Сообщений: 146
Завершенные тесты: 1
15.12.2013, 13:46     Определить число безопасных стопок #4
Цитата Сообщение от firefox123 Посмотреть сообщение
vndtta, но a, b, c не даны ведь
тогда для всех a,b,c надо посчитать и сложить - это цикл по a и еще 1 вложенный по b
в принципе для всех а можно придумать формулу тогда будет 1 цикл по а
надо подумать

Добавлено через 22 минуты
C++
1
2
3
4
5
6
7
int factorial(int x)
{
int res=1;
 for(int i=2;i<=x;i++)
  res*=i;
 return res;
}
C++
1
2
3
4
5
6
7
8
9
10
int sum;
for(int a=0,sum=0;a<=(n+1)/2;a++)
{
 int space=(a-1>0)?a-1:0;
 for(int b=0;b<=n-a;b++)
 {
  c=n-a-b;
  sum+=factorial(n-space)/factorial(a)/factorial(b)/factorial(c);
 }
}
с одним циклом не знаю пока как
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
15.12.2013, 14:10     Определить число безопасных стопок #5
Если время выполнения программы не сильно важно, то можно рекурсией:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
using namespace std;
int rec(int p, int col, int n)
{
    if(col==n)
        return 1;
    int t=rec(2,col+1,n)+rec(3,col+1,n);
    if(p!=1)
        t+=rec(1,col+1,n);
    return t;
}
 int main()
 {
     int n;
     cin>>n;
     cout<<rec(1,1,n)+rec(2,1,n)+rec(3,1,n);     
     return 0;
 }
vndtta
66 / 43 / 5
Регистрация: 17.10.2011
Сообщений: 146
Завершенные тесты: 1
15.12.2013, 14:28     Определить число безопасных стопок #6
Цитата Сообщение от vndtta Посмотреть сообщение
тогда для всех a,b,c надо посчитать и сложить - это цикл по a и еще 1 вложенный по b
в принципе для всех а можно придумать формулу тогда будет 1 цикл по а
надо подумать

Добавлено через 22 минуты
C++
1
2
3
4
5
6
7
int factorial(int x)
{
int res=1;
 for(int i=2;i<=x;i++)
  res*=i;
 return res;
}
C++
1
2
3
4
5
6
7
8
9
10
int sum;
for(int a=0,sum=0;a<=(n+1)/2;a++)
{
 int space=(a-1>0)?a-1:0;
 for(int b=0;b<=n-a;b++)
 {
  c=n-a-b;
  sum+=factorial(n-space)/factorial(a)/factorial(b)/factorial(c);
 }
}
с одним циклом не знаю пока как
я вспомнил треугольник паскаля и ц меня получилось вот что

http://www.cyberforum.ru/cgi-bin/latex.cgi?\sum_{b+c=n-a}^{}(b+c)!/b!/c!={2}^{n-a}
тогда у нас остается 1 цикл по а
C++
1
2
3
4
5
6
int sum;
for(int a=0,sum=0;a<=(n+1)/2;a++)
{
 int space=(a-1>0)?a-1:0;
 sum+=factorial(n-space)/factorial(a)*pow(2,n-a);
}
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
15.12.2013, 14:37     Определить число безопасных стопок #7
вот более быстрый способ с помощью ДП:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
 
 int main()
 {
     int n, j, i, s=0;
     cin>>n;
     int a[20][3];
     a[0][0]=a[0][1]=a[0][2]=1;
     for(i=1; i<n; i++)
     {
         a[i][0]=a[i-1][1]+a[i-1][2];
         a[i][2]=a[i][1]=a[i-1][0]+a[i-1][1]+a[i-1][2];
     }
     for(i=0; i<3; i++)
         s+=a[n-1][i];
     cout<<s<<endl;
     return 0;
 }
vndtta
66 / 43 / 5
Регистрация: 17.10.2011
Сообщений: 146
Завершенные тесты: 1
15.12.2013, 17:56     Определить число безопасных стопок #8
Цитата Сообщение от vndtta Посмотреть сообщение
я вспомнил треугольник паскаля и ц меня получилось вот что

http://www.cyberforum.ru/cgi-bin/latex.cgi?\sum_{b+c=n-a}^{}(b+c)!/b!/c!={2}^{n-a}
тогда у нас остается 1 цикл по а
C++
1
2
3
4
5
6
int sum;
for(int a=0,sum=0;a<=(n+1)/2;a++)
{
 int space=(a-1>0)?a-1:0;
 sum+=factorial(n-space)/factorial(a)*pow(2,n-a);
}
у меня тут ошибка
должно быть
sum+=factorial(n-space)/factorial(a)/factorial(n-space-a)*pow(2,n-a);

Добавлено через 56 секунд
Цитата Сообщение от valeriikozlov Посмотреть сообщение
вот более быстрый способ с помощью ДП:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
 
 int main()
 {
     int n, j, i, s=0;
     cin>>n;
     int a[20][3];
     a[0][0]=a[0][1]=a[0][2]=1;
     for(i=1; i<n; i++)
     {
         a[i][0]=a[i-1][1]+a[i-1][2];
         a[i][2]=a[i][1]=a[i-1][0]+a[i-1][1]+a[i-1][2];
     }
     for(i=0; i<3; i++)
         s+=a[n-1][i];
     cout<<s<<endl;
     return 0;
 }
очень интересно, поясни плз из каких соображений вывел

Добавлено через 27 минут
Цитата Сообщение от valeriikozlov Посмотреть сообщение
вот более быстрый способ с помощью ДП:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
 
 int main()
 {
     int n, j, i, s=0;
     cin>>n;
     int a[20][3];
     a[0][0]=a[0][1]=a[0][2]=1;
     for(i=1; i<n; i++)
     {
         a[i][0]=a[i-1][1]+a[i-1][2];
         a[i][2]=a[i][1]=a[i-1][0]+a[i-1][1]+a[i-1][2];
     }
     for(i=0; i<3; i++)
         s+=a[n-1][i];
     cout<<s<<endl;
     return 0;
 }
я разобрался
тут тогда можно заменить 2 последних массива на 1
получится
a[0][0]=1
a[0][1]=2
a[i][0]=a[i-1][1]
a[i][1]=a[i-1][0]+a[i-1][1]=a[i-2][1]+a[i-1][1]

это простой ряд фибоначчи

http://www.cyberforum.ru/cgi-bin/latex.cgi?{a}_{1}=3={F}_{4}
http://www.cyberforum.ru/cgi-bin/latex.cgi?{a}_{i}={F}_{i+3}

Добавлено через 24 минуты
тут как то неправильно с рялами фибоначчи

http://www.cyberforum.ru/cgi-bin/latex.cgi?{x}_{-1}=1;<br />
{x}_{0}=2;<br />
{x}_{i}=2*({x}_{i-1}+{x}_{i-2});<br />
{a}_{i}={x}_{i-1}+{x}_{i-2};<br />
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
15.12.2013, 18:41     Определить число безопасных стопок #9
Цитата Сообщение от firefox123 Посмотреть сообщение
Подскажите, как решить? Если бы не было стопок С, то ответом было бы число Фибоначчи.
если есть стопки С, то un+2 = 2*(un+1+un), почти Фибоначчи, соответственно решение будет такое:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <cstdio>
using namespace std;
 
int main()
{
    int c[ 20 ] = { 1, 3, 0 };
    int n;
 
    for ( int i = 2; i < N; ++i )
                    c[ i ] = 2 * c[ i - 2 ] + 2 * c[ i - 1 ];
    scanf( "%d", &n );
    printf( "%d\n", c[ n ] );
    return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.12.2013, 19:27     Определить число безопасных стопок
Еще ссылки по теме:

C++ Дано натуральное число х. Определить кратно ли это число 2, 3, 5
C++ Ввести произвольное целое положительное число. Определить число с обратным порядком цифр заданного числа
C++ Дано трицифровое число.Определить имеет ли число одинаковые первую и последнюю цифры

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
firefox123
0 / 0 / 0
Регистрация: 17.11.2013
Сообщений: 39
15.12.2013, 19:27  [ТС]     Определить число безопасных стопок #10
Спасибо всем, задачу сдал.
Yandex
Объявления
15.12.2013, 19:27     Определить число безопасных стопок
Ответ Создать тему
Опции темы

Текущее время: 13:59. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru