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

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

Войти
Регистрация
Восстановить пароль
 
Gepar
1177 / 533 / 20
Регистрация: 01.07.2009
Сообщений: 3,517
#1

Полоска - C++

25.04.2013, 14:19. Просмотров 940. Ответов 5
Метки нет (Все метки)

Есть задание, которое я не могу понять:
Задана полоска длиной 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.
Но блин, я всё равно ничего не понял Чего хотят-то, ну есть полоска, которую я допустим представлю в виде массива, ну пронумерую я её в начале, а чего выводить и чего считать мне не ясно Помогите понять объяснив словестно или подкиньте пожалуйста кусок кода с++ если вы владете паскалем.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.04.2013, 14:19
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Полоска (C++):

Полоска - ActionScript
У меня проблема На одном кадре уменя есть полоска и кнопка. Начальная ширина полоски = 1. Но прина жатие на кнопку полоса увиличивает...

Градиентная полоска - PHP
имеем код: &lt;? echo &quot;&lt;table rules=none border=1;&gt;&lt;tr&gt;&quot;; $rd = 88; $em = 100 - $rd; $x = 0; $y = 0; while ($x&lt;$rd) { echo...

полоска в Chrome - Спутниковая связь
только-что открыл Хром и заметил черную тоненькую полоску внизу: пробовал переустановить и отключать расширения - ничего не...

Переливающаяся полоска - HTML, CSS
Смутил довольно не сложный момент, но все не могу придумать как сделать и в каком направлении копать, пытался через css3:animation, но чет...

полоска репутации - JavaScript
подскажите как написать такую полоску как вконтакте полоска репутации, только у меня она будет максимально 100%, да ещё цвет изменялся...

Белая полоска внизу - HTML, CSS
Помогите пожалуйста, при уменьшение расширения появляется белая полоска внизу. Я новенький, извините за глупый вопрос. Вот демка...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
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 клеток, найти закономерность.
1
Gepar
1177 / 533 / 20
Регистрация: 01.07.2009
Сообщений: 3,517
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;
            
    }
0
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;
            
    }
Ну, возможно. У меня мозг перестает работать после третьего сгибания, а вырезать бумажки нехочу)
0
Gepar
1177 / 533 / 20
Регистрация: 01.07.2009
Сообщений: 3,517
25.04.2013, 21:53  [ТС] #5
Цитата Сообщение от veverix Посмотреть сообщение
У меня мозг перестает работать после третьего сгибания
Так они же начиная с первого сгибания происходят одинаково: согнул, первернул то что согнул и т.д
Хотя я тоже это не понял, я просто написал по тому словестному описанию решения и сверился что результаты получаю правильные, так я до сих пор и не понял зачем мы их там каждый раз переворачиваем.
0
FallofUsher
0 / 0 / 0
Регистрация: 28.04.2014
Сообщений: 2
02.06.2014, 23:25 #6
Gepar, а как ты реализовывал класс Item? такую же задачу делаю, правда на c#, но никак разобраться не могу
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.06.2014, 23:25
Привет! Вот еще темы с ответами:

Странная полоска на экране - Мониторы
Здравствуйте! У меня проблема (а может и нет). Сегодня обнаружил на левой стороне монитора вертикальную полоску в виде тонкого...

Черная полоска на мониторе - Мониторы
Здравствуйте! Имеется монитор BenQ EW2740l, недавно заметил, что при включении компьютера, вверху экрана, появилось , как бы незаполненное...

Полоска в меню пуск - Windows 7
Добрый день! Как убрать эту странную полоску в Windows 7 RTM?

Появилась непонятная полоска( - HTML, CSS
Ребят, подскажите! Если на сайте: http://noviyhudozhnik.ru/ пройти в &quot;Войти - регистрация&quot;, &quot;Войти - восстановить пароль&quot; то справа...


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

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

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