[Информатика] Задача
|
|
xomach | Дата: Четверг, 06 Июня 2013, 16:05:14 | Сообщение # 1 |
7 уровень
Группа: Проверенные
Сообщений: 484
Награды: 0
Репутация: 128
Блокировки: ![](/scripts/images/ic_info.gif)
| Сильно меня эта задача подставила одиныжды, интересно теперь, как решается: Дан массив длины 2^N - 1, содержащий попарно различные целые числа от 1 до 2^N - 1 и обладающий свойством кучи (с минимумом в корне), а также целое число K (1< K < 2^N - 1). На какой позиции в массиве может находиться число K? Обоснуйте ваш ответ.
|
|
|
|
BinGO | Дата: Четверг, 06 Июня 2013, 20:52:18 | Сообщение # 2 |
Группа: Модераторы
Сообщений: 2906
Награды: 8
Блокировки: ![](/scripts/images/ic_info.gif)
| Цитата (xomach) попарно различные Цитата (xomach) обладающий свойством кучи (с минимумом в корне) Цитата (xomach) (1< K < 2^N - 1) !?!?!?
|
|
|
|
xomach | Дата: Пятница, 07 Июня 2013, 09:12:57 | Сообщение # 3 |
7 уровень
Группа: Проверенные
Сообщений: 484
Награды: 0
Репутация: 128
Блокировки: ![](/scripts/images/ic_info.gif)
| 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
Блокировки: ![](/scripts/images/ic_info.gif)
| http://ru.wikipedia.org/wiki/Куча_(структура_данных) Цитата (xomach) (1< K < 2^N - 1) Очевидно, <=
У самого пока идей по решению нет.
|
|
|
|
xomach | Дата: Пятница, 07 Июня 2013, 15:40:46 | Сообщение # 5 |
7 уровень
Группа: Проверенные
Сообщений: 484
Награды: 0
Репутация: 128
Блокировки: ![](/scripts/images/ic_info.gif)
| Цитата (SirNikolas) Очевидно, <= Да это не важно. Вообще задача со вступительных в одно место, из-за нее меня взяли на одну параллель ниже( очевидным кажется, что позиция K в полуинтервале [ 2^(trunc(log2K)-1) ; 2^(trunc(log2K)+2) ) Но доказать я это не смог
Сообщение отредактировал xomach - Пятница, 07 Июня 2013, 17:33:27 |
|
|
|
BinGO | Дата: Пятница, 07 Июня 2013, 19:51:37 | Сообщение # 6 |
Группа: Модераторы
Сообщений: 2906
Награды: 8
Блокировки: ![](/scripts/images/ic_info.gif)
| Я все-равно не понимаю идеи задачи. Имеется одномерный массив. А как это он упорядочен кучей? Если смотреть по той схеме, что в статье на википедии, то я не понимаю.
|
|
|
|
xomach | Дата: Пятница, 07 Июня 2013, 20:15:21 | Сообщение # 7 |
7 уровень
Группа: Проверенные
Сообщений: 484
Награды: 0
Репутация: 128
Блокировки: ![](/scripts/images/ic_info.gif)
| смотри, вот пример кучи из задачи: .....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
Блокировки: ![](/scripts/images/ic_info.gif)
| 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
Блокировки: ![](/scripts/images/ic_info.gif)
| Цитата (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
|
|
|
|