Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Для новичков > Программа "ОФИЦЕРЫ"

Автор: IBMcorp 12.5.2011, 12:51

Подсчитать количество способов расставить j слонов на доске nxn.

Я на сайте http://e-maxx.ru/algo/bishops_arrangement нашел довольно неплохое объяснение её но при попытки реализации выводит ошибку в строчке vector < vector<int> > d (n*2, vector<int> (k+2));
//error: 'vector' was not declared in this scorp //Подскажите пожалуйста как исправить эту ошибку и что автор делает с её помощью.
Вот мой код :

Код


#include <iostream>
#include <sstream>
#include <string>
#include <vector>
int cells (int i) 
{
if (i & 1)
return i / 4 * 2 + 1;
else
return (i - 1) / 4 * 2 + 2;
}
int main()
{

int n, k; 
scanf("%d%d",&n,&k);
if (k > 2*n-1) {
printf("0");
return 0;
}

vector < vector<int> > d (n*2, vector<int> (k+2));
for (int i=0; i<n*2; ++i)
d[i][0] = 1;
d[1][1] = 1;
for (int i=2; i<n*2; ++i)
for (int j=1; j<=k; ++j)
d[i][j] = d[i-2][j] + d[i-2][j-1] * (cells(i) - j + 1);

int ans = 0;
for (int i=0; i<=k; ++i)
ans += d[n*2-1][i] * d[n*2-2][k-i];
printf("%d",ans);

return 0;
}

Извиняюсь если этот вопрос уже задавали и ли данную задачу пожалуйста киньте ссылку на эту тему.[code=cpp]

Автор: triclosan 12.5.2011, 12:58

мож std::vector ?

Автор: IBMcorp 12.5.2011, 13:50

std::vector- это как я понял создание контейнера? я просто впервые встречаюсь с данной операцией

Автор: bsa 12.5.2011, 14:06

IBMcorp, шаблон vector находится в пространстве имен std. Поэтому, при каждом упоминании этого контейнера (шаблона) следует указывать std:: перед ним. Или написать сразу после инклюдов using namespace std;, но это не очень хорошо, хотя для маленьких программ подойдет.

Цитата(IBMcorp @ 12.5.2011, 13:50

)

std::vector- это как я понял создание контейнера?

std::vector - это ШАБЛОН контейнера "вектор". std::vector<int> - это ТИП контейнера "вектор", содержащего объекты типа int. std::vector<int> IntVector(10, 1); - это ПЕРЕМЕННАЯ типа std::vector<int> изначально содержащая в себе 10 элементов типа int, имеющих значение 1.

Автор: IBMcorp 12.5.2011, 14:23

спасибо за объяснение. 1) При вводе после инклудов using namespace std; ошибка с векторами отпала програма запускается но при попытки ввода значенией происходит завершение работы программы.
2) vector < vector<int> > d (n*2, vector<int> (k+2)); В этой строке я так понял происходит создание массива а я могу её заменить просто на int d[n*2][k+2]; ?

Автор: bsa 12.5.2011, 14:32

IBMcorp, теоретически можешь, если n и k константы известные на момент компиляции

Автор: IBMcorp 12.5.2011, 14:39

сработало но опять же програма запускается но когда он мне выдает окно и я ввожу значения происходит завершение работы программы.

при вводе значений на прямую в коде вроде все нормально даже значения какието выводит а есть какой-то способ проверить программу??

при вводе n = 8 и k= 8 получается отрицательное число(

Код


#include <iostream>
#include <sstream>
#include <string>
#include <vector>
int cells (int i)
 {
    if (i & 1)
        return i / 4 * 2 + 1;
    else
        return (i - 1) / 4 * 2 + 2;
}
int main()
{

  int n, k;
 n=8;
 k= 9;
if (k > 2*n-1)
 {
    printf("0");
    return 0;
}
 int d[n*2][k+2];
for (int i=0; i<n*2; ++i)
    d[i][0] = 1;
d[1][1] = 1;
for (int i=2; i<n*2; ++i)
    for (int j=1; j<=k; ++j)
        d[i][j] = d[i-2][j] + d[i-2][j-1] * (cells(i) - j + 1);

int ans = 0;
for (int i=0; i<=k; ++i)
    ans += d[n*2-1][i] * d[n*2-2][k-i];
printf("%d",ans);

    return 0;
}

Автор: bsa 12.5.2011, 14:48

конечно есть - отладка называется. Запускаешь в режиме отладки и выполняешь ее построчно.

Автор: IBMcorp 12.5.2011, 15:53

эх что то корявые значения у меня получаются при записи через int d[n*2][k+2]; получаются отрицательные числа а при записи через vector < vector<int> > d (n*2, vector<int> (k+2)); способов расставить 1 офицера меньше чем 10
хотя в принципе количество способов расставить одного офицера он выдает правильно 64 а остальное ...

Автор: IBMcorp 12.5.2011, 18:01

СПАСИБО ОГРОМНОЕ ЗА РАЗЪЯСНЕНИЕ все идеально работает вот код программы если кому понадобится

Код


#include <iostream>
#include <sstream>
#include <string>
#include <vector>
using namespace std;
int cells (int i)
 {
    if (i & 1)
        return i / 4 * 2 + 1;
    else
        return (i - 1) / 4 * 2 + 2;
}
int main()
{

  int n, k;
  scanf("%d%d",n,k);
if (k > 2*n-1)
 {
    printf("0");
    return 0;
}
vector < vector<int> > d (n*2, vector<int> (k+2));
for (int i=0; i<n*2; ++i)
    d[i][0] = 1;
d[1][1] = 1;
for (int i=2; i<n*2; ++i)
    for (int j=1; j<=k; ++j)
        d[i][j] = d[i-2][j] + d[i-2][j-1] * (cells(i) - j + 1);

int ans = 0;
for (int i=0; i<=k; ++i)
    ans += d[n*2-1][i] * d[n*2-2][k-i];
printf("%d",ans);

    return 0;
}

Автор: borisbn 12.5.2011, 18:37

IBMcorp, а чтобы нагяднее и понятнее было бы с векторами используй typedef. смотри:
было

Цитата

vector < vector<int> > d (n*2, vector<int> (k+2));

стало

Код


typedef vector<int> IntVector;
vector< IntVector > d( n*2, IntVector( k + 2 ) );

Вот уж никогда бы не подумал, что когда-нибудь буду советовать IBM Corporation smile

Автор: IBMcorp 13.5.2011, 00:40

а можно как-нибудь обойтись без этой строчки vector < vector<int> > d (n*2, vector<int> (k+2)); ну в смысле задать её по другому это же вроде по сути создание массива я попробывал её задать как int d[n*2][k+2]; но там появились отрицательные числа

P.s. числа на момент компиляции известны

Автор: volatile 13.5.2011, 01:11

Цитата(IBMcorp @ 13.5.2011, 00:40

)

можно как-нибудь обойтись без этой строчки vector < vector<int> >
...
P.s. числа на момент компиляции известны

Если n и k являются компайл тайм константами, и вы хотите использовать не вектор, а просто массив, то
int d[n*2][k+2];
вполне легальный код.

Цитата(IBMcorp @ 13.5.2011, 00:40

)

но там появились отрицательные числа

повторяю, Если n и k известны, какие и где отрицательные числа появились?

Добавлено через 5 минут и 49 секунд
Упс.. smile

посмотрел ваш код в начале

Цитата(IBMcorp @ 12.5.2011, 12:51

)

int n, k;
scanf("%d%d",n,k);

Вовсе они не известны на момент компиляции.
Так что, уточните ваши противоречивые высказывания.

Автор: IBMcorp 13.5.2011, 01:53

Код


#include <sstream>
#include <string>
#include<stdio.h>
int cells (int i)
 {
    if (i & 1)
        return i / 4 * 2 + 1;
    else
        return (i - 1) / 4 * 2 + 2;
}
int main()
{
int n=2, k=1;
 if (k > 2*n-1)
 {
    printf("0");
    return 0;
}
int d[n*2][ k + 2];
for (int i=0; i<n*2; ++i)
    d[i][0] = 1;
d[1][1] = 1;
for (int i=2; i<n*2; ++i)
    for (int j=1; j<=k; ++j)
        d[i][j] = d[i-2][j] + d[i-2][j-1] * (cells(i) - j + 1);

int ans = 0;
for (int i=0; i<=k; ++i)
    ans += d[n*2-1][i] * d[n*2-2][k-i];
printf("%d",ans);

    return 0;
}

в конкретно в данном случае(доска 2на2; 1 офицер) должен вывести 4 способа а он вы водит чуть ли не 2а миллиарда

Автор: volatile 13.5.2011, 02:55

Цитата(IBMcorp @ 13.5.2011, 01:53

)

должен вывести 4 способа а он вы водит чуть ли не 2а миллиарда

У вас проблема с инициализацией массива.
При инициализации его нулями, выводит как и положено 4.
int d[n*2][ k + 2] = {0};
Все остальное не менял.
http://liveworkspace.org/code/2241df74ec37643440ea1242d274cd80
В логику работы не вникал. Разберитесь сначала с ней.

Автор: borisbn 13.5.2011, 06:29

А чтобы обнулить векторы, т.е. массивы с заранее неизвестным размером, сделай так

Код


 typedef vector < int > IntVector;
vector < IntVector > d ( n * 2 , IntVector ( k + 2, 0 ) ) ; // , 0 в конце

Автор: IBMcorp 13.5.2011, 13:38

volatile спасибо большое!!! на других значениях тоже все отлично работает
Всем остальным тоже огромное спасибо за разъяснение и потраченное время

Автор: bsa 13.5.2011, 14:29

M
bsa

IBMcorp, если ответ на вопрос получен, то пометь тему решенной