|
[Информатика] Задача
|
|
| 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 |
|
Группа: Модераторы
Сообщений: 2906
Награды: 8
Блокировки: | Цитата (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 |
|
Группа: Модераторы
Сообщений: 2906
Награды: 8
Блокировки: | Я все-равно не понимаю идеи задачи.
Имеется одномерный массив. А как это он упорядочен кучей? Если смотреть по той схеме, что в статье на википедии, то я не понимаю.
|
| |
|
|
| 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
|
| |
|
|
