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

Расстановка кирпичей - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.64
Джон
0 / 0 / 0
Регистрация: 06.03.2012
Сообщений: 40
19.03.2012, 01:10     Расстановка кирпичей #1
Сколькими способами можно замостить 3xn прямоугольник при помощи 2x1 доминошек? Ниже наведен пример замощения такими плитками прямоугольника 3x12.
Вот задачаhttp://www.e-olimp.com.ua/problems/482 Помогите, плиз. Все остальные задачи, которые задали, сделал.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
19.03.2012, 09:08     Расстановка кирпичей #2
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include "stdio.h"
int main()
{
   freopen("input.txt", "rt", stdin);
 freopen("output.txt", "wt", stdout);
   int n, i, j, mas[5][33];
   while(true)
   {
       scanf("%d", &n);
       if(n==-1)
           break;
       for(i=0; i<5; i++)
           for(j=0; j<33; j++)
               mas[i][j]=0;
       if(n%2!=0)
           printf("0\n");
       else
       {
           mas[0][0]=1;
           for(i=0; i<n; i++)
           {
               if(i<n-1)
                   mas[0][i+2]+=mas[0][i];
               mas[3][i]+=mas[0][i];
               mas[4][i]+=mas[0][i];
               mas[0][i+1]+=mas[1][i];
               mas[0][i+1]+=mas[2][i];
               mas[4][i+1]+=mas[1][i];
               mas[3][i+1]+=mas[2][i];
               mas[1][i+1]+=mas[4][i];
               mas[2][i+1]+=mas[3][i];
           }
           printf("%d\n", mas[0][n]);
       }
   }
   
 return 0;
 }
Джон
0 / 0 / 0
Регистрация: 06.03.2012
Сообщений: 40
20.03.2012, 00:22  [ТС]     Расстановка кирпичей #3
я дико извиняюсь, но можете еще объяснить, что значат эти двухмерные массивы??
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
20.03.2012, 02:01     Расстановка кирпичей #4
Цитата Сообщение от Джон Посмотреть сообщение
но можете еще объяснить, что значат эти двухмерные массивы??
я в решении этой задачи использовал 5 возможных вариантов, которые могут быть в текущей тройке (точка это пустая клетка, звездочка заполненная):
все три очередный клетки могут быть пустыми:
.
.
.
следующий вариант:
*
.
.
следующий вариант:
.
.
*
следующий вариант:
*
*
.
следующий вариант:
.
*
*
Вариант когда все три заполненные я не рассматривал - учитывал что следующие три клетки пустые.
Джон
0 / 0 / 0
Регистрация: 06.03.2012
Сообщений: 40
20.03.2012, 11:01  [ТС]     Расстановка кирпичей #5
наверное, вопрос тупой, но что именно значат элементы этого двухмерного массива?
vndtta
66 / 43 / 5
Регистрация: 17.10.2011
Сообщений: 146
Завершенные тесты: 1
20.03.2012, 11:54     Расстановка кирпичей #6
тут не надо никаких массивов
простая последовательность
F(n+2)=F(2)*F(n)+2F(n-2)+..+2F(2);
F(2)=3;

F(n+2)=3*F(n)+2(F(n-2)+F(n-4)+...)
F(n+2)=3*F(n)+(F(n)-F(n-2))=4F(n)-F(n-2)

Добавлено через 18 минут
Цитата Сообщение от vndtta Посмотреть сообщение
тут не надо никаких массивов
простая последовательность
F(n+2)=F(2)*F(n)+2F(n-2)+..+2F(2);
F(2)=3;

F(n+2)=3*F(n)+2(F(n-2)+F(n-4)+...)
F(n+2)=3*F(n)+(F(n)-F(n-2))=4F(n)-F(n-2)
ой я тут двойку забыл на самом деле вот так должно быть
F(n+2)=F(2)*F(n)+2F(n-2)+..+2F(2)+2F(0);
F(2)=3; F(0)=1
Джон
0 / 0 / 0
Регистрация: 06.03.2012
Сообщений: 40
20.03.2012, 17:39  [ТС]     Расстановка кирпичей #7
а как это реализовать?
vndtta
66 / 43 / 5
Регистрация: 17.10.2011
Сообщений: 146
Завершенные тесты: 1
21.03.2012, 17:29     Расстановка кирпичей #8
Цитата Сообщение от Джон Посмотреть сообщение
а как это реализовать?
примерно так..

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;
 
int main(){
 int prev1=1;
 int prev2=3;
 int result,n;
 cout<<"vvedite 4islo"<<endl;
 cin>>i;
 if (i%2 !=0) {cout<<"nepodhodit"<<endl; return 0;}
 if (i==0) {cout<<prev1<<endl; return 0;}
 if (i==2) {cout<<prev2<<endl; return 0;}
 for(int i=2;i<n;i+=2){
  result=4*prev2-prev1;
  prev1=prev2;
  prev2=result;
 }
 cout<<result<<endl;
 return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.02.2015, 22:38     Расстановка кирпичей
Еще ссылки по теме:

Расстановка ссылок в списке через цикл C++
Расстановка кораблей (морской бой) C++
Расстановка знаков операций C++

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

Или воспользуйтесь поиском по форуму:
okman
 Аватар для okman
15 / 21 / 1
Регистрация: 05.04.2013
Сообщений: 203
10.02.2015, 22:38     Расстановка кирпичей #9
скажите, пожалуйста, откуда вы вывели эту формулу?
Yandex
Объявления
10.02.2015, 22:38     Расстановка кирпичей
Ответ Создать тему
Опции темы

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