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

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

Войти
Регистрация
Восстановить пароль
 
artlinenn
0 / 0 / 0
Регистрация: 15.02.2013
Сообщений: 58
#1

Списки. Стеки. Очереди - C++

09.03.2013, 22:57. Просмотров 1076. Ответов 3
Метки нет (Все метки)

Квадрат разбит на http://www.cyberforum.ru/cgi-bin/latex.cgi?{4}^{k} равновеликих квадратных клеток. Квадрат перегибается поочередно относительно вертикальной (правая половина подкладывается под левую) и горизонтальной (нижняя половина подкладывается под верхнюю) оси симметрии до тех пор, пока все клетки не будут расположены друг под другом. Требуется занумеровать клетки исходного квадрата таким образом, чтобы в результате выполнения операций перегиба номера клеток, расположенных друг под другом, образовали числовую последовательность 1,2,3,...,http://www.cyberforum.ru/cgi-bin/latex.cgi?{4}^{k}, начиная с верхней клетки.

Добавлено через 4 минуты
Есть такая же задача с решением: http://mf.grsu.by/UchProc/ztasks/olimp/dstruct/z5
но мне нужна работающая программа на C++
буду благодарен (с меня +)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.03.2013, 22:57
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Списки. Стеки. Очереди (C++):

Списки, стеки, очереди - C++
В процессе разбора этой темы появились программки на список. Сделанные через класс, не идеал конечно, но вроде бы и не самый плохой...

Задача на тему Стеки, очереди, деки, списки, кольца - C++
Программа на вход получает список школьников следующего вида: 9 Иванов 10 Петров 11 Сидоров 9 Григорьев ...

Списки, Стеки,Очереди (На сколько кусков распадется оставшаяся часть листа? ) - C++
Доброго всем времени суток!! Помогите написать программу: Из листа клетчатой бумаги размером М*N клеток удалили некоторые клетки. На...

Очереди и стеки - C++
#include "stdafx.h" #include "iostream" using namespace std; struct stack { int x; stack *Next,*Head; ...

C++ Стеки, Очереди - C++
Дан целочисленный массив размера N. Преобразовать его, прибавив к нечетным числам последний элемент. Последний элемент массива не изменять....

Стеки и очереди - C++
Ребят, помогите справится с заданием. Задача 6. Система состоит из процессора P, трёх очередей F0, F1, F2 и стека S. В систему...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
artlinenn
0 / 0 / 0
Регистрация: 15.02.2013
Сообщений: 58
14.03.2013, 12:09  [ТС] #2
Помогите, люди добрые))
SummerRain
326 / 325 / 17
Регистрация: 16.12.2012
Сообщений: 544
14.03.2013, 16:21 #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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
//Квадрат разбит на 4^k равновеликих квадратных клеток. Квадрат перегибается поочередно относительно вертикальной 
//(правая половина подкладывается под левую) и горизонтальной (нижняя половина подкладывается под верхнюю) 
//оси симметрии до тех пор, пока все клетки не будут расположены друг под другом. 
//Требуется занумеровать клетки исходного квадрата таким образом, 
//чтобы в результате выполнения операций перегиба номера клеток, расположенных друг под другом, 
//образовали числовую последовательность 1,2,3,...,4 ^ k, начиная с верхней клетки.
 
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <iterator>
#include <cmath>
 
struct point
{
    int value;
    int x, y;
    point (int X, int Y) : x(X), y(Y), value(0) {}
    point (int X, int Y, int val) : x(X), y(Y), value(val) {}
};
 
size_t numberOfDigits(size_t n) {
    size_t count = 0;
    while (n != 0) {
        n /= 10;
        ++count;
    }
    return count;
}
 
// горизонтальный сгиб
void horizFold(std::vector<point>** mass, size_t curlen) {
    // добавляем точки
    for (size_t i = 0; i < curlen / 2; ++i) {
        for (size_t j = 0; j < curlen; ++j) {
            std::copy(mass[curlen - i - 1][j].rbegin(), mass[curlen - i - 1][j].rend(), back_inserter(mass[i][j]));
        }
    }
    // очищаем поля
    for (size_t i = curlen / 2; i < curlen; ++i) {
        for (size_t j = 0; j < curlen; ++j) {
            mass[i][j].clear();
        }
    }
}
 
// вертикальный сгиб
void vertFold(std::vector<point>** mass, size_t curlen) {
    // добавляем точки
    for (size_t i = 0; i < curlen; ++i) {
        for (size_t j = 0; j < curlen / 2; ++j) {
            std::copy(mass[i][curlen - j - 1].rbegin(), mass[i][curlen - j - 1].rend(), back_inserter(mass[i][j]));
        }
    }
    // очищаем поля
    for (size_t i = curlen; i < curlen; ++i) {
        for (size_t j = 0; j < curlen / 2; ++j) {
            mass[i][j].clear();
        }
    }
}
 
int main()
{
    size_t k;    // степень четвёрки
    std::cout << "Enter k" << std::endl;
    std::cin >> k;
    size_t len = (size_t)pow(2.0, 1.0 * k);  // длина стороны квадрата
 
    // подсчитаем количество цифр максимального номера квадрата, для читаемого вывода
    size_t numOfDig = numberOfDigits((size_t)pow(4.0, 1.0 * k));  
 
    int** originalMass = new int*[len];  // тот массив, который мы захотим получить
    for (size_t i = 0; i < len; ++i) {
        originalMass[i] = new int[len];
    }
 
    std::vector<point>** mass = new std::vector<point>*[len];  // создадим массив векторов точек
    for (size_t i = 0; i < len; ++i) {
        mass[i] = new std::vector<point>[len];
    }
 
    for (size_t i = 0; i < len; ++i) {
        for (size_t j = 0; j < len; ++j) {
            mass[i][j] = std::vector<point>(1, point(i, j));  // и каждый элемент этого массива инициализируем вектором
        }                                                 // из одной точки, 
    }                                              // в которую сохраним координаты текущего элемента массива
 
    size_t curlen = len;   // текущая длина
 
    while (curlen != 1) {               // "сгибаем" массив до тех пор, пока он не станет одной клеткой
        vertFold(mass, curlen);
        horizFold(mass, curlen);
        curlen /= 2;
    }
 
    // после всех сгибов у нас все точки окажутся в векторе, который хранится в верхнем левом элемента массива mass[0][0]
    for (size_t i = 0; i < mass[0][0].size(); ++i) {
        // придадим значение каждой точке этого вектора в обратном порядке, т.к. начальный элемент вектора находится "внизу"
        (mass[0][0])[i].value = mass[0][0].size() - i;  
        // заполняем наш исходный массив (заполнение элементов массива идёт в порядке расположения точек в векторе)
        originalMass[(mass[0][0])[i].x][(mass[0][0])[i].y] = (mass[0][0])[i].value;
    }
 
    // выводим искомый массив и получаем пронумерованный квадрат
    for (size_t i = 0; i < len; ++i) {
        for (size_t j = 0; j < len; ++j) {
            std::cout << std::setw(numOfDig + 1) << originalMass[i][j];
        }
        std::cout << std::endl;
    }
 
    system("PAUSE>0");
    return 0;
}
artlinenn
0 / 0 / 0
Регистрация: 15.02.2013
Сообщений: 58
14.03.2013, 17:40  [ТС] #4
SummerRain, спасибо большое)))
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.03.2013, 17:40
Привет! Вот еще темы с ответами:

Стеки, очереди, массивы - C++
Помогите реализовать стек с помощью двух очередей, используя массивы (операции удаления, добавления).

Бинарные деревья, очереди, стеки - C++
#include &lt;iostream&gt; // подключение библиотеки ввода-вывода #include &lt;conio.h&gt; // подключение библиотеки функций работы с консолью ...

4 задания по С++ (Бинарные деревья. Стеки,очереди) - C++
1. В текстовом файле записана без ошибок формула вида: цифра или М(формула, формула), или m(формула, формула), где M обозначает функцию...

Указатели,стеки списки. - C++
Здравствуйте помогите решить две задачи на Си++,заранее спасибо! Указатели, работа с динамическими структурами данных. Динамическое...


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

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

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