[Информатика] Задача

xomach

Дата: Четверг, 06 Июня 2013, 16:05:14 | Сообщение # 1

7 уровень

Группа: Проверенные

Сообщений: 484

Награды: 0

Репутация: 128

Блокировки:

Сильно меня эта задача подставила одиныжды, интересно теперь, как решается:
Дан массив длины 2^N - 1, содержащий попарно различные целые числа от 1 до 2^N - 1 и обладающий
свойством кучи (с минимумом в корне), а также целое число K (1< K < 2^N - 1). На какой позиции
в массиве может находиться число K? Обоснуйте ваш ответ.

Бильярд в варкрафте
Конструктор скиллов

BinGO

Дата: Четверг, 06 Июня 2013, 20:52:18 | Сообщение # 2

Цитата (xomach)

попарно различные

Цитата (xomach)

обладающий свойством кучи (с минимумом в корне)

Цитата (xomach)

(1< K < 2^N - 1)

!?!?!?

xomach

Дата: Пятница, 07 Июня 2013, 09:12:57 | Сообщение # 3

7 уровень

Группа: Проверенные

Сообщений: 484

Награды: 0

Репутация: 128

Блокировки:

BinGO, если конечно это чем-то поможет:

Цитата (xomach)

попарно различные

Нет 2ух одинаковых

Цитата (xomach)

(1< K < 2^N - 1)

просто ограничения на K: больше 1, но меньше длины массива

Цитата (xomach)

обладающий свойством кучи (с минимумом в корне)

а тут сложно

Бильярд в варкрафте
Конструктор скиллов

Сообщение отредактировал xomach - Пятница, 07 Июня 2013, 09:19:35

SirNikolas

Дата: Пятница, 07 Июня 2013, 13:32:21 | Сообщение # 4

Группа: Модераторы

Сообщений: 6729

Награды: 1

Репутация: 1867

Блокировки:

http://ru.wikipedia.org/wiki/Куча_(структура_данных)

Цитата (xomach)

(1< K < 2^N - 1)

Очевидно, <=

У самого пока идей по решению нет.

Автоматическое удаление утечек
Библиотека для работы с двоичными числами
Создание массивов с произвольным индексированием
Чтоб модераторы души в вас не чаяли

xomach

Дата: Пятница, 07 Июня 2013, 15:40:46 | Сообщение # 5

7 уровень

Группа: Проверенные

Сообщений: 484

Награды: 0

Репутация: 128

Блокировки:

Цитата (SirNikolas)

Очевидно, <=

Да это не важно.
Вообще задача со вступительных в одно место, из-за нее меня взяли на одну параллель ниже(
очевидным кажется, что позиция K в полуинтервале
[ 2^(trunc(log2K)-1) ; 2^(trunc(log2K)+2) )
Но доказать я это не смог

Бильярд в варкрафте
Конструктор скиллов

Сообщение отредактировал xomach - Пятница, 07 Июня 2013, 17:33:27

BinGO

Дата: Пятница, 07 Июня 2013, 19:51:37 | Сообщение # 6

Я все-равно не понимаю идеи задачи.
Имеется одномерный массив. А как это он упорядочен кучей? Если смотреть по той схеме, что в статье на википедии, то я не понимаю.

xomach

Дата: Пятница, 07 Июня 2013, 20:15:21 | Сообщение # 7

7 уровень

Группа: Проверенные

Сообщений: 484

Награды: 0

Репутация: 128

Блокировки:

смотри, вот пример кучи из задачи:
.....01
..02....03
04 05 06 07
...
Так N этажей.

вот еще пример:

.....01
..02....04
03 05 06 07
...

тут каждое число от 1 до макс. 1 раз встречается. 1 всегда в корне.

Бильярд в варкрафте
Конструктор скиллов

Сообщение отредактировал xomach - Пятница, 07 Июня 2013, 20:16:00

SirNikolas

Дата: Пятница, 07 Июня 2013, 20:23:27 | Сообщение # 8

Группа: Модераторы

Сообщений: 6729

Награды: 1

Репутация: 1867

Блокировки:

BinGO, дан массив a[1 .. 2^N], забитый неповторяющимися числами от 1 до 2^N, причем a[i] < a[2 * i], a[i] < a[2 * i + 1] для любых i от 1 до 2^(N - 1).

xomach

Дата: Суббота, 08 Июня 2013, 06:09:04 | Сообщение # 9

7 уровень

Группа: Проверенные

Сообщений: 484

Награды: 0

Репутация: 128

Блокировки:

Цитата (xomach)

позиция K в полуинтервале
[ 2^(trunc(log2K)-1) ; 2^(trunc(log2K)+2) )

чушь(

................01
........02............06
....03.....07.....08....09
..04 10 11 12 13 14 15 16
.05 ...

Добавлено (08 Июня 2013, 06:09:04)
---------------------------------------------
ну точно, верхняя планка для позиции K ∈ [1;N] = 2^K-1. Для K>N = 2^N-1

Бильярд в варкрафте
Конструктор скиллов