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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.56
firefox123
0 / 0 / 0
Регистрация: 17.11.2013
Сообщений: 39
#1

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

15.12.2013, 12:03. Просмотров 1419. Ответов 9
Метки нет (Все метки)

При переработке радиоактивных материалов образуются отходы трех видов — особо опасные (тип 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 число Фибоначчи.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.12.2013, 12:03
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Определить число безопасных стопок (C++):

Подскажите алгоритм сортировки трех стопок разноцветных книг - C++
Значится так, имеются книги с обложками трех цветов. Есть три стопки книг, в каждой стопке от 1 до N книг, 3 разных цветов и в случайном...

Дано шестизначное натуральное число. Определить число сотен и десятков в нем - C++
help Дано шестизначное натуральное число. Определить число сотен и десятков в нем. (Visual studio C++)

Дано натуральное четырехзначное число n. Определить, является ли это число перевертышем - C++
Дано натуральное четырехзначное число n. Определить, является ли это число перевертышем. Например, числа 2222, 6116, 0440 и т.д.

Дано трицифровое число.Определить имеет ли число одинаковые первую и последнюю цифры - C++
Дано трицифровое число. Определить что число имеет одинаковые первую и последнюю цифры (131, 272 и т.д.) Без циклов.Нужно сделать...

Найти максимальное число в массиве и определить, сколько цифр числа делятся на число Z - C++
Массив intA=

Методом обхода в глубину определить число компонент связности и цикломатическое число графа - C++
Методом обхода в глубину определить число компонент связности и цикломатическое число графа – минимальное число ребер, которые надо...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
vndtta
90 / 67 / 13
Регистрация: 17.10.2011
Сообщений: 235
Завершенные тесты: 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)
1
firefox123
0 / 0 / 0
Регистрация: 17.11.2013
Сообщений: 39
15.12.2013, 13:15  [ТС] #3
vndtta, но a, b, c не даны ведь
0
vndtta
90 / 67 / 13
Регистрация: 17.10.2011
Сообщений: 235
Завершенные тесты: 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);
 }
}
с одним циклом не знаю пока как
1
valeriikozlov
Эксперт C++
4670 / 2496 / 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;
 }
1
vndtta
90 / 67 / 13
Регистрация: 17.10.2011
Сообщений: 235
Завершенные тесты: 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);
}
1
valeriikozlov
Эксперт C++
4670 / 2496 / 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;
 }
2
vndtta
90 / 67 / 13
Регистрация: 17.10.2011
Сообщений: 235
Завершенные тесты: 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 />
0
ya_noob
_
201 / 145 / 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;
}
0
firefox123
0 / 0 / 0
Регистрация: 17.11.2013
Сообщений: 39
15.12.2013, 19:27  [ТС] #10
Спасибо всем, задачу сдал.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.12.2013, 19:27
Привет! Вот еще темы с ответами:

Определить, сколько пар (положительное число, отрицательное число) находятся в начале массива - C++
Дан целочисленный массив B. Определить, сколько пар (положительное число, отрицательное число) находятся в начале массива.

Определить число положительных и число отрицательных элементов в массиве - C++
В произвольно заданном одномерном массиве определить число положительных и число отрицательных элементов. Сформировать новый массив из...

Дано натуральное число n (n>99). Определить число сотен внем - C++
Дано натуральное число n (n&gt;99). Определить число сотен внем. на паскале это выглядит такprogram z64; {$APPTYPE CONSOLE} uses ...

Дано натуральное число х. Определить кратно ли это число 2, 3, 5 - C++
Разработать программу, использующую разветвления в visual c++ 6.0 с коментариями


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
15.12.2013, 19:27
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru