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

Полоска - C++

Восстановить пароль Регистрация
 
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,508
25.04.2013, 14:19     Полоска #1
Есть задание, которое я не могу понять:
Задана полоска длиной 2^k клеток и шириной в одну клетку. Полоску сгибают пополам так, чтобы правая половинка оказалась под левой. Сгибание продолжают до тех пор, пока сверху находится больше одной клетки. Необходимо пронумеровать клетки таким образом, чтобы после окончания сгибания полосы номера клеток в получившейся колонке были расположены в порядке 1,2,3,4,...,2^k.

Это какая-то олимпиадная задачка, я нашёл в сети решение на паскале:


Будем моделировать сложение полоски, затем пронумеруем получившуюся колонку клеток числами от 1 до 2n, после чего распечатаем числа, приписанные первой, второй, ..., 2^n-ой клетке исходной полоски.
Сначала создаем двусвязный список, состоящий из 2^k элементов. Поле next будет указывать на элемент находящийся под данным, а поле last - на элемент находящийся над данным. Для верхнего элемента last=0, а для нижнего next=n+1, где n-общее число элементов. Вначале длина верхней полоски равняется n элементов, после первого сгибания их она станет n/2, после второго - n/4, и т.д. Пусть в данный момент длина верхней полоски есть cn элементов. Значит нам необходимо cn/2 правых элементов опустить под cn/2 левых. Для этого запустим цикл, который будет менять i от 1 до cn/2 и на каждом шаге помещать (cn-i+1)-ю колонку элементов под i-ю, при этом порядок элементов в (cn-i+1)-ой колонке меняется на противоположный. После каждого сгибания cn уменьшается вдвое. Так продолжаем до тех пор пока cn>1.

Pascal
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
{$A-,B-,D-,E+,F-,I-,L-,N-,O-,R-,S-,V-}
{$M 65520,0,655360}
uses crt;
const
maxk = 13; {Максимальное значение для k}
type
input = record
last,next,new : word;
end;
var
k,i,j,n,cn,half : word;
m : array[1..1 shl maxk] of input;
Procedure concat(a,b : word);
var i,j,nj : word;
begin
i:=a;while m[i].next<>n+1 do i:=m[i].next;
j:=b; while m[j].next<>n+1 do j:=m[j].next;
while j<>0 do
begin
nj:=m[j].last; m[i].next:=j; m[j].last:=i; i:=j; j:=nj;
end;
m[i].next:=n+1;
end;
begin
Write('Enter k...');readln(k);
n:=1 shl k; {Определение длины полоски}
for i:=1 to n do{Начальные значения}
with m[i] do
begin
last:=0;
next:=n+1;
new:=0;
end;
cn:=n;
while cn>1 do {Сгибание полоски}
begin
half:=cn div 2;
for i:=1 to half do concat(i,cn-i+1);
cn:=half;
end;
j:=1;
for i:=1 to n do {Нумерация клеток}
begin
m[j].new:=i; j:=m[j].next;
end;
for i:=1 to n do write(m[i].new:5);
writeln;
end.
Но блин, я всё равно ничего не понял Чего хотят-то, ну есть полоска, которую я допустим представлю в виде массива, ну пронумерую я её в начале, а чего выводить и чего считать мне не ясно Помогите понять объяснив словестно или подкиньте пожалуйста кусок кода с++ если вы владете паскалем.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.04.2013, 14:19     Полоска
Посмотрите здесь:

Windows 7 Полоска в меню пуск
Черная полоска на мониторе!
JavaScript полоска репутации
Градиентная полоска PHP
ActionScript Полоска
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
veverix
39 / 39 / 2
Регистрация: 14.09.2012
Сообщений: 85
25.04.2013, 18:39     Полоска #2
Мне кажется так:

Имеет полоску, допустим, из 4 клеток:

1 2 3 4

Сгибаем по середине - имеем как бы две полоски, каждая в два раза меньше.

12
43

Опять сгибаем:

1
4
3
2

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

Ну и теперь - все предыдущие номера - это индексы массива. Записываем по индексам порядковый номер в колонке.

Решить подобную задачу для лент в 8 и 16 клеток, найти закономерность.
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,508
25.04.2013, 19:02  [ТС]     Полоска #3
veverix, да я уже написал читая то описание решения что я постил выше, правда немного с индексами там намудрили, но сам не понимая что надо сделать делая то что там писали получил вроде то что надо. По крайней мере результаты выдаёт такие же как и паскалевская версия так что вроде всё ок.
Моё решение приняло следующий вид:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
    Item* items = new Item[size];
    
    //создаём начальную полоску
    for(int i=0;i<size; i++)
        items[i].number = i+1;
 
    //запоминаем нач. размер
    int nowSize = size;
    //пока сгибается полоска
    while(nowSize / 2)
    {
        //сгибаем её, предварительно "развернув" задом-наперёд сгибаемые элементы
        for(int i=0;i<nowSize/2;i++)
            add(&items[i] , flip(items+nowSize-i-1));
 
        //уменьшаем размер в два раза
        nowSize /= 2;
            
    }
veverix
39 / 39 / 2
Регистрация: 14.09.2012
Сообщений: 85
25.04.2013, 19:10     Полоска #4
Цитата Сообщение от Gepar Посмотреть сообщение
veverix, да я уже написал читая то описание решения что я постил выше, правда немного с индексами там намудрили, но сам не понимая что надо сделать делая то что там писали получил вроде то что надо. По крайней мере результаты выдаёт такие же как и паскалевская версия так что вроде всё ок.
Моё решение приняло следующий вид:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
    Item* items = new Item[size];
    
    //создаём начальную полоску
    for(int i=0;i<size; i++)
        items[i].number = i+1;
 
    //запоминаем нач. размер
    int nowSize = size;
    //пока сгибается полоска
    while(nowSize / 2)
    {
        //сгибаем её, предварительно "развернув" задом-наперёд сгибаемые элементы
        for(int i=0;i<nowSize/2;i++)
            add(&items[i] , flip(items+nowSize-i-1));
 
        //уменьшаем размер в два раза
        nowSize /= 2;
            
    }
Ну, возможно. У меня мозг перестает работать после третьего сгибания, а вырезать бумажки нехочу)
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,508
25.04.2013, 21:53  [ТС]     Полоска #5
Цитата Сообщение от veverix Посмотреть сообщение
У меня мозг перестает работать после третьего сгибания
Так они же начиная с первого сгибания происходят одинаково: согнул, первернул то что согнул и т.д
Хотя я тоже это не понял, я просто написал по тому словестному описанию решения и сверился что результаты получаю правильные, так я до сих пор и не понял зачем мы их там каждый раз переворачиваем.
FallofUsher
 Аватар для FallofUsher
0 / 0 / 0
Регистрация: 28.04.2014
Сообщений: 2
02.06.2014, 23:25     Полоска #6
Gepar, а как ты реализовывал класс Item? такую же задачу делаю, правда на c#, но никак разобраться не могу
Yandex
Объявления
02.06.2014, 23:25     Полоска
Ответ Создать тему
Опции темы

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