Сейчас 12:48:00 Пятница, 9 декабря, 2022 год
[ x ] Главная ⇒ Форум ⇐ RSS Файлы Cтатьи Картинки В о й т и   или   з а р е г и с т р и р о в а т ь с я


[ Новые сообщения · Участники · Правила форума · Поиск · RSS ]
  • Страница 1 из 1
  • 1
Модератор форума: Malfatto, Ty3uK  
Форум о Warcraft 3 » Просто общение » Компьютеры и железо » [Информатика] Задача
[Информатика] Задача
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


 

Форум о Warcraft 3 » Просто общение » Компьютеры и железо » [Информатика] Задача
  • Страница 1 из 1
  • 1
Поиск:

Copyright © 2006 - 2022 Warcraft3FT.info При копировании материалов c сайта ставьте, пожалуйста, активную обратную ссылку на нас • Design by gReeB04ki ©
Хостинг от uCoz