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

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

Форум программистов > Центр помощи > [C++] Заполнение матрицы по спирали

Автор: DasBit 3.1.2010, 20:22

Люди помогите пожалуйста smile

Задали задачку, нужно заполнить матрицу размером 4x4 по спирали начиная с центра случайными числами. Я начало сделал, но дальше не знаю как. Помогите пожалуйста. И если можно то с объяснениями, где, что и для чего мы делаем т.к. хотелось бы не просто здать задачу и получить оценку но и самому разобраться как это делаеться smile

Вот мой код:

Код


#include <iostream>
#include <time.h>
#include <stdlib.h>
using namespace std;
void main()
{
srand(time(NULL));
const int row=4;
const int col=4;
int x,y;
int mas[row][col];
int start;
cout<<"x = ";
cin>>x; //Вводим минимальное значение сгенерированного случайного числа
cout<<"y = ";
cin>>y;//Вводим максимальное значение сгенерированного случайного числа

Все...дальше ступор smile

Автор: zim22 3.1.2010, 20:36

Цитата(DasBit @ 3.1.2010, 19:22

)

нужно заполнить матрицу размером 4x4 по спирали начиная с центра с

мне просто интересно, где в матрице 4на4 центр? в какой точке?

Автор: kemiisto 3.1.2010, 20:45

Цитата(zim22 @ 3.1.2010, 21:36

)

мне просто интересно, где в матрице 4на4 центр? в какой точке?

Видимо, подразумевалось, что если заполнять по спирали, то в качестве "центра" можно выбрать любой элемент из [2, 2], [2, 3], [3, 2], [3, 3].

Автор: DasBit 3.1.2010, 21:36

Имееться в виду любая точка из центрального квадрата:
[1,1];[1,2];[2,1];[2,2];
Я пытался разобраться в задаче, взяв за стартовую точку [2,1] В тетради все расписал как координата изменяеться, но так и не смог найти никакой закономерности :(

Автор: zim22 3.1.2010, 21:38

как по мне - эта задача красиво решается с помощью рекурсии.
начиная с левого верхнего угла квадрата мы строим спираль по часовой стрелке. в конце концов спираль "закрутится" и в момент закручивания как раз пойдут обратные вызовы рекурсивной функции, которая и будет заполнять квадратики числами.

Автор: DasBit 3.1.2010, 21:42

Мы к сожалению рекурсию еще не учили. Но мне препод подсказал, что задача состоит из двух циклов, и большого количества условий

Автор: zim22 3.1.2010, 21:46

Цитата(DasBit @ 3.1.2010, 20:42

)

Мы к сожалению рекурсию еще не учили

ну так прояви смекалку. выучи её. и препод похвалит, и перед однокурсниками похвастаешься.

ещё вариант "рекурсии без рекурсии"
алгоритм тот же самый, только на каждом шагу ты в дополнительный массив индекс текущего "обходного" элемента записываешь.
когда подошёл к самому последнему(закрученному) элементу - занеси его значение тоже в массив. и после этого цикл по этому дополнительному массиву в обратном порядке.
и каждому элементу значение нужное тебе присваиваешь.

Автор: DasBit 3.1.2010, 21:56

Цитата(zim22 @ 3.1.2010, 21:46)

Цитата(DasBit @ 3.1.2010, 20:42

)

Мы к сожалению рекурсию еще не учили

Извените, мож я немного торможу, но я толком ничего не понял из того что вы мне сказали. Можно кратенький разьяснительный код ? smile

Добавлено через 3 минуты и 39 секунд
И еще препод сказал, что в этой задачке есть какая то закономерность, найдя ее задача очень легко решаеться, но я сколько не смотрел, закономерность нашел только одну: Сумма координатных точек идет попеременно четное, нечетное число. Но логики честно говоря я в этом никакой не вижу :(

Автор: zim22 3.1.2010, 22:02

ты должен придумать алгоритм, которые будет обходить элементы массива по спирали
в итоге он должен в таком порядке обойти все элементы:
1   2   3   4
12  13  14  5
11  16  15  6
10  9   8   7

и на каждом шаге обхода - ты записываешь индекс матрицы текущего обходного элемента во вспомогательный массив.
после того, как ты дойдёшь до 16 элемента - берёшь и считываешь в обратном порядке элементы из вспомогательного массива. эти элементы - это индексы для заполнения:
начиная с центра спирали.

Автор: DasBit 3.1.2010, 22:08

Спасибо большое smile

я бы до такого никогда не додумался. Буду сейчас пробовать ))

Автор: DasBit 5.1.2010, 15:15

Я сделал кое какие наброски программы, но препод сказал, что почти правильно. Вместо циклов это все нужно делать через if'ы. Плдскажите плз как, я не пойму

Код


#include <iostream>
#include <time.h>
#include <stdlib.h>
using namespace std;
void main()
{
srand(time(NULL));
const int row=4;
const int col=4;
int x,y;
int mas[row][col];
int start;
cout<<"x = ";
cin>>x; //Вводим минимальное значение сгенерированного случайного числа
cout<<"y = ";
cin>>y;//Вводим максимальное значение сгенерированного случайного числа
for (j=0;j<row-1;j++)
  {
    cout<<"tmas["<<i<<","<<j<<"]"<<endl;
  }
for (i=0;i<col-1;i++)
  {
    cout<<"tmas["<<i<<","<<j<<"]"<<endl;
  } 
for (j=row-1;j>0;j--)
  {
    cout<<"tmas["<<i<<","<<j<<"]"<<endl;
  } 
for (i=col-1;i>0;i--)
  {
    cout<<"tmas["<<i<<","<<j<<"]"<<endl;
  }
i++;
for (j=0;j<row-2;j++)
  {
    cout<<"tmas["<<i<<","<<j<<"]"<<endl;
  } 
}

cout'ы с выводом сообщения делал для того чтобы просто проследить правильность передвижения по матрице

Автор: zim22 5.1.2010, 16:13

Цитата(DasBit @ 5.1.2010, 14:15

)

Плдскажите плз как, я не пойму

задавай свои вопросы в "http://forum.vingrad.ru/forum/forum-471.html". там тебе быстрей ответят.
в Центр Помощи пишут халявщики, которые хотят чтобы за них всё сделали.

Автор: DasBit 5.1.2010, 16:33

Ну даделайте тогда просто эту задачку, если вам не сложно smile

Просто я честно говоря уже устал копаться в этом коде, он мне сниться скора начнет smile

А когда wmid разблокируют отблогодарю))

Автор: DasBit 5.1.2010, 18:16

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

Автор: Dov 5.1.2010, 19:37

Цитата(DasBit @ 5.1.2010, 17:16

)

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

А что тут комментировать? Следи за перемещениями по индексам и всё. Или тебя за ручку водить надо? Маленький что-ли? smile

Код

int main()
{
    const int    ROW    = 4;
    const int    COL    = 4;
    int          matr[ROW][COL];
    int          i, j;

    // "закручиваем спираль..."    
    cout << "for matrix: " << ROW << " x " << COL << endl << endl;    
    int    rowBeg    = 0;
    int    rowEnd    = ROW - 1;
    int    colBeg    = 0; 
    int    colEnd    = COL - 1;
    int    count    = ROW * COL;
    while(count)
    {
        for(i = colBeg; i <= colEnd && count; i++)
            matr[rowBeg][i] = count--;
        rowBeg++;
        for(i = rowBeg; i <= rowEnd && count; i++)
            matr[i][colEnd] = count--;
        colEnd--;
        for(i = colEnd; i >= colBeg && count; i--)
            matr[rowEnd][i] = count--;        
        rowEnd--;
        for(i = rowEnd; i >= rowBeg && count; i--)
            matr[i][colBeg] = count--;
        colBeg++;
    }
    
    for(i = 0; i < ROW; i++)
    {
        for(j = 0; j < COL; j++)
            cout << setw(3) << matr[i][j];
        cout << endl;
    }

    // "раскручиваем..."
    cout << "\n\nits items in spiral order are:\n\n";    
    rowBeg = 0;
    rowEnd = ROW - 1;
    colBeg = 0; 
    colEnd = COL - 1;
    count  = ROW * COL;    
    while(count)
    {
        for(i = colBeg; i <= colEnd && count; i++, count--)
            cout << matr[rowBeg][i] << ' ';
        rowBeg++;        
        for(i = rowBeg; i <= rowEnd && count; i++, count--)
            cout << matr[i][colEnd] << ' ';
        colEnd--;        
        for(i = colEnd; i >= colBeg && count; i--, count--)
            cout << matr[rowEnd][i] << ' ';
        rowEnd--;        
        for(i = rowEnd; i >= rowBeg && count; i--, count--)
            cout << matr[i][colBeg] << ' ';
        colBeg++;
    }
    cout << endl << endl;
    return 0;
}

Автор: DasBit 5.1.2010, 23:30

Оу пасиб ! В коде разобрался smile