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

Занумеровать клетки исходного квадрата следующим образом - C++

Восстановить пароль Регистрация
 
curtis65
0 / 0 / 0
Регистрация: 14.04.2013
Сообщений: 12
14.04.2013, 21:29     Занумеровать клетки исходного квадрата следующим образом #1
Помогите кто сможет!!
Задали реализовать задачу на с++.А с чего начать просто не понимаю.В плюсах я конечно не спец,но в такой задачи я даже не знаю с чего начать.
Пробовал найти,есть реализация на Delphi,ф на плюсах так и не смог((

Задание:

Квадрат разбит на 4k равновеликих квадратных клеток. Квадрат перегибается поочередно относительно вертикальной (правая половина подкладывается под левую) и горизонтальной (нижняя половина подкладывается под верхнюю) оси симметрии до тех пор, пока все клетки не будут расположены друг под другом. Требуется занумеровать клетки исходного квадрата таким образом, чтобы в результате выполнения операций перегиба номера клеток, расположенных друг под другом, образовали числовую последовательность 1,2,3,...,4k, начиная с верхней клетки.

Буду весь благодарен!!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.04.2013, 21:29     Занумеровать клетки исходного квадрата следующим образом
Посмотрите здесь:

C++ Напечатать числа следующим образом:
Напечатать числа следующим образом C++
Заполнить массив следующим образом C++
C++ Записать числа следующим образом
Матрицу K(m, n) заполнить следующим образом C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
abit
 Аватар для abit
260 / 259 / 33
Регистрация: 03.02.2013
Сообщений: 709
14.04.2013, 22:03     Занумеровать клетки исходного квадрата следующим образом #2
В принципе как решить эту задачу я понял и даже было сел писать алгоритм... но потом увидел:
Квадрат разбит на 4k равновеликих квадратных клеток.
это подстава...
допустим k=2, значит квадрат разбит на 8 равных квадратов? мне в голову не приходит ни одного способа как это сделать и можно ли вообще это сделать ...

мой вариант годится только для 4^k

проверьте условие
curtis65
0 / 0 / 0
Регистрация: 14.04.2013
Сообщений: 12
15.04.2013, 15:19  [ТС]     Занумеровать клетки исходного квадрата следующим образом #3
Извиняюсь,ошибся
именно для 4^k
Вы были абсолютно правы)

Добавлено через 15 часов 6 минут
abit, ты смог бы помочь мне?а то я совсем задание не понимаю
w8me
496 / 11 / 1
Регистрация: 10.04.2013
Сообщений: 44
15.04.2013, 16:58     Занумеровать клетки исходного квадрата следующим образом #4
Та же задача только раскладывается до прямой , buff[0][0] -> buff[3][3] и будет искомый квадрат
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
39
40
41
42
43
#define k 4
#define m (1<<k)
int buff[m][m] = {0};
 
int main(int argc, _TCHAR* argv[])
{
    int i,x,y;
    int pas_row, pas_col;
    int row_src, col_src, row_des, col_des;
    int row_end, col_end;
 
    for(i=0;i<m;i++)
        buff[i][0] = i+1;
 
    for(i=0;i<k;i++)
    {
        pas_row = 1<<(k-i-1);
        row_end = 1<<(k-i);
        for(x=0;x<=pas_row-1;x++)
        {
            pas_col = 1<<i; 
            col_end = 1<<i; 
 
            for(y=0;y<pas_col;y++)
            {
                row_src = row_end - x - 1;
                col_src = col_end - y - 1; 
                row_des = x; 
                col_des = pas_col + y;
                buff[row_des][col_des] = buff[row_src][col_src];
            }
        }
    }
    FILE *fout;
    fout = fopen("Log.txt","wt");
    for(x=0;x<m;x++)
    {
        for(y=0;y<m;y++) fprintf(fout, "%3d ", buff[x][y]);
        fprintf(fout, "\n");
    }
    fclose(fout); 
        return 0;
}
curtis65
0 / 0 / 0
Регистрация: 14.04.2013
Сообщений: 12
15.04.2013, 17:07  [ТС]     Занумеровать клетки исходного квадрата следующим образом #5
w8me, а где именно эту запись нужно вставлять?
w8me
496 / 11 / 1
Регистрация: 10.04.2013
Сообщений: 44
15.04.2013, 17:13     Занумеровать клетки исходного квадрата следующим образом #6
Вместо этого
C++
1
2
3
4
5
6
7
8
    FILE *fout;
    fout = fopen("Log.txt","wt");
    for(x=0;x<m;x++)
    {
        for(y=0;y<m;y++) fprintf(fout, "%3d ", buff[x][y]);
        fprintf(fout, "\n");
    }
    fclose(fout);
Вставьте это
C++
1
2
3
4
5
6
    for (int i=0; i<k; i++)
    {
        for (int j=0; j<k; j++)
            printf("%3d ", buff[i][j]);
        printf("\n");
    }
abit
 Аватар для abit
260 / 259 / 33
Регистрация: 03.02.2013
Сообщений: 709
15.04.2013, 17:44     Занумеровать клетки исходного квадрата следующим образом #7
abit, ты смог бы помочь мне?а то я совсем задание не понимаю
]

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

суть того, что я придумал такая:
создать трёх-мерный контейнер vector< vector < vector < int > > >, аналог ( трёхмерного массива ) допустим A[i][j][z] = j*k+i;
забить его по приниципу
i - номер квадрата по X [0..k)
j - номер квадрата по Y [0..k)
z - для всех элементов оставить нулевым

процесс N-ого (N-номер складывания от 1 до k-1) складывания по вертикали - добавлять все элементы в A[0..4^(k-N)) [0..k) [p] из A[4^(k-N)..4^(k-N-1)) [0..k) [всё что есть тут]
процесс M-ого складывания по вертикали - аналогично добавлять все элементы в
A [0..k) [0..4^(k-M)) [p] из A [0..k) [4^(k-M)..4^(k-M-1)) [всё что есть тут]

в конце вы получите в A[0][0][1..4^k] набор чисел, если их все запихнуть в map <size_t,size_t>
где first элемент (ключ) будет само число, а second-элемент - индекс в массиве A[0][0][1..4^k], то получите решение задачи, по обращению к map например mymap [0] он вам выдаст какой номер нужно написать на 1-м квадрате, mymap[1] - на втором и т.д.

в общем мне кажется что я слишком много лишних структур привлёк, но тем не менее это решение в лоб
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.04.2013, 13:55     Занумеровать клетки исходного квадрата следующим образом
Еще ссылки по теме:

Заполнить массив A следующим образом: C++
Заполнить массив А следующим образом C++
C++ Заполнить массив следующим образом

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

Или воспользуйтесь поиском по форуму:
curtis65
0 / 0 / 0
Регистрация: 14.04.2013
Сообщений: 12
20.04.2013, 13:55  [ТС]     Занумеровать клетки исходного квадрата следующим образом #8
abit, к сожалению это задание не верно(
мог ты мне помочь? с алгоритмами я плохо дружу((
Yandex
Объявления
20.04.2013, 13:55     Занумеровать клетки исходного квадрата следующим образом
Ответ Создать тему
Опции темы

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