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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.64
Джон
0 / 0 / 0
Регистрация: 06.03.2012
Сообщений: 40
#1

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

19.03.2012, 01:10. Просмотров 1553. Ответов 10
Метки нет (Все метки)

Сколькими способами можно замостить 3xn прямоугольник при помощи 2x1 доминошек? Ниже наведен пример замощения такими плитками прямоугольника 3x12.
Вот задачаhttp://www.e-olimp.com.ua/problems/482 Помогите, плиз. Все остальные задачи, которые задали, сделал.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.03.2012, 01:10
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Расстановка кирпичей (C++):

«Расстановка кубиков» - C++
Программа играющая в игру «Расстановка кубиков». Игральный кубик можно перекатывать по клеткам поля n*m. Причём, если клетка имеет вес i,...

Расстановка 8 ферзей - C++
Привет всем, слушайте, вот исходник на С++ задача <<о восьми ферзях>>: #include<iostream> #include<cmath> #include"pent" void...

Расстановка знаков операций - C++
Не получается решить задачу,не могу понять в чем проблема.Вроде все правильно все выводит,но проваливает почти все тесты.Помогите найти в...

Расстановка знаков препинания - C++
По правилу расстановки знаков препинания перед каждым знаком препинания пробел отсутствует, а после него обязательно стоит пробел. Учитывая...

Расстановка игральных костей - C++
Программа играющая в игру «Расстановка игральных костей». Задана частичная двумерная сетка. В некоторых позициях сетки расставлены...

Расстановка скобок в условном операторе - C++
Никак не могу понять где поставить скобки(begin end), чтобы если квадраты чисел равны не выводилось второе сообщение. #include...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
valeriikozlov
Эксперт C++
4670 / 2496 / 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 / 0
Регистрация: 06.03.2012
Сообщений: 40
20.03.2012, 00:22  [ТС] #3
я дико извиняюсь, но можете еще объяснить, что значат эти двухмерные массивы??
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
20.03.2012, 02:01 #4
Цитата Сообщение от Джон Посмотреть сообщение
но можете еще объяснить, что значат эти двухмерные массивы??
я в решении этой задачи использовал 5 возможных вариантов, которые могут быть в текущей тройке (точка это пустая клетка, звездочка заполненная):
все три очередный клетки могут быть пустыми:
.
.
.
следующий вариант:
*
.
.
следующий вариант:
.
.
*
следующий вариант:
*
*
.
следующий вариант:
.
*
*
Вариант когда все три заполненные я не рассматривал - учитывал что следующие три клетки пустые.
0
Джон
0 / 0 / 0
Регистрация: 06.03.2012
Сообщений: 40
20.03.2012, 11:01  [ТС] #5
наверное, вопрос тупой, но что именно значат элементы этого двухмерного массива?
0
vndtta
90 / 67 / 13
Регистрация: 17.10.2011
Сообщений: 235
Завершенные тесты: 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
1
Джон
0 / 0 / 0
Регистрация: 06.03.2012
Сообщений: 40
20.03.2012, 17:39  [ТС] #7
а как это реализовать?
0
vndtta
90 / 67 / 13
Регистрация: 17.10.2011
Сообщений: 235
Завершенные тесты: 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;
}
0
okman
15 / 21 / 1
Регистрация: 05.04.2013
Сообщений: 204
10.02.2015, 22:38 #9
скажите, пожалуйста, откуда вы вывели эту формулу?
0
_sitizen_
0 / 0 / 0
Регистрация: 27.04.2014
Сообщений: 4
05.02.2017, 23:06 #10
Цитата Сообщение от vndtta Посмотреть сообщение
F(n+2)=F(2)*F(n)+2F(n-2)+..+2F(2)+2F(0);
F(2)=3; F(0)=1
нельзя ли уточнить немного: F(n+2)=F(2)*F(n)+2*F(n-2) при добавлении 2 клеток, нужно предыдущее кол-вол способов умножить на 3 за счет расстановки плиток в добавленных ячейках, а также возможна расстановка 2 типов в последних 4 столбиках ячеек, это ясно. Но откуда берутся остальные слагаемые???
0
vndtta
90 / 67 / 13
Регистрация: 17.10.2011
Сообщений: 235
Завершенные тесты: 1
17.02.2017, 16:44 #11
Цитата Сообщение от _sitizen_ Посмотреть сообщение
Но откуда берутся остальные слагаемые???
для такой же расстановки в 6 столбиках, 8 столбиках и т.д., когда доминошка лежит горизонтально между парными столбиками типа такого
6
Код
 =:= =:= =:=
[] =:= =:= []
[] =:= =:= []
8
Код
 =:= =:= =:= =:=
[] =:= =:= =:= []
[] =:= =:= =:= []
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.02.2017, 16:44
Привет! Вот еще темы с ответами:

Расстановка кораблей (морской бой) - C++
Доброго времени суток, при расстановке 2х палубных кораблей возникает проблема... При выборе точки уже занятой, система ломается и...

Расстановка html тегов в тексте - C++
Хочу спросить, реально ли сделать автоматический перевод и правильную расстановку html тегов в русском тексте. Я мучился мучился, но так и...

Консольный морской бой. Расстановка кораблей - C++
Добрый вечер, уважаемые форумчане. Хочу написать консольный морской бой. Начал с функции автоматической расстановки кораблей. Весь...

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


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

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

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