Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 03.10.2008, 01:13
Новичок

Отправить личное сообщение для Megov Посмотреть профиль Найти все сообщения от Megov
 
Регистрация: 17.02.2008
Сообщений: 14

Помогите разобраться с задачей
Объясните, пожалуйста, задачи 2 и 3 отсюда : http://algolist.ru/olimp/sor_prb.php. Меня интересует математическое доказательство того, как все это работает. А если разница должна быть, к примеру, 1,25 или 1,05, то сколько камней класть и в какую кучу?

Заранее благодарен.
  #2  
Старый 07.10.2008, 18:15
гость

 
Сообщений: n/a

Допустим камни весом от 0 до 1. А теперь теперь возьми кучу с максимальным весом камней
к примеру c = {1,1,1,1,1,1,1,1}.
А теперь возьми две кучи a и b.
Теперь кидай в каждую кучу камни, сравнивая в какой меньше - туда и кидаем. Посуди сам в этом случае кучи примерно будут равны. Одна пытается догнать другую.При этом разница между ними будет будет 1 ;
тем более отношение - заведомо <=1 (меньшая/большую). Заметь, если взять кучу с большим числом камней то отношение будет стремиться к 1
или равно ему Проверь сам - возьми 10000 камней (a/b = 1) , 10001 камень (a/b~0.9999999). Теперь возьми небольшую кучу с камнями от 0 до 1. Заметь разница между ними по-прежнему не может быть больше 1;
И небольше самого большого камня в общей куче незавимимо от того в каком месте кучи он стоит. Это потому что, ты положил самый большой камень например в кучу a , то куча b будет плюсовать к себе дальнейшие
камни пока не перегонит a, НО! разница между кучами не будет больше
веса самого большого камня.(потом кучи пытаются догнать друг друга и камней побольше самого бол. -нет) Проверь сам.
Сам подумай, если камни от 0 до 1, то разница между кучами ними <=1.
Отношение между кучами будет разное в зависимости от того где сам. б. камень лежит в куче.
Вот о вопросе о том почему самый большой камень нужен вначале.
Опять просто возьми кучу из 3 камней с{1,1,1}.Смотри,
самый большой получился =1,

куча а = 1
куча b = 1+1 или наоборот

это минимум камней при котором условие выполняется с максимальным весом !!! обрати внимание.
отношение между кучами = 0.5 или 2 не больше,
если в общей куче увеличить кол-во камней то отношение будет меняться в сторону 1. a/b = 0.5 максимум отношения.
теперь если оставить камень max=1. а остальные <1 то , занеся 1 в кучу a , потом будешь заносить в кучу b пока она не перегонит a. потом наоборот итд итп.
вариант с кучей {1,1,1} является максимальным по этому поводу:
минимальное кол-во камней при котором a/b =0.5 и камни по весу максимальны.
Теперь куча{0.1,0.6,1, 0.4,0.4} . Сам.б. = 1;
1:
a = 1
b = 0.1+0.6+0.4 =1.1
это минимум камней при котором условие выполняется с максимальным весом !!!
2:
a = 1+0.4 = 1.4;
b = 1.1

a/b <=0.5;

Сам.б. камень положен первым , тогда другая куча сначала догоняет первую пока не пергонит, потом у них отношение будет <0.5. единственный вариант когда отношение будет = 0.5 - читай выше.
Я не учитываю условия когда в одной куче 1 а в другой 0.4 , это уже сам учтешь.
Если ты хочешь чтобы у тебя было отношение = 3/2.
максимум: с {1,1,1,1,1}. ты ложишь один сам.б. камень в одну кучу, два последующих сам. больщих в другую.
вот.

a = 1 +1
b = 1+1 +1

a/b = 2/3 или b/2 = 3/2 = 1.5 раза, тогда взяв меньшие веса в куче b/a<1.5

если надо наложи в кучи сначала столько 1 чтобы их отношение = m/n
m - колво макс. камней в первой
т - во второй или наоборот.

С весами меньшими все также. все будет работать.
Только еслу нужно определенное отношение просто накидай в уме в обе кучи столько камней с максимальным весом чтобы их отношение было тем которое нужно.

например
3/5

a = 1+1+1;
b = 1+1+1+1+1;
это максим.веса.

а = .8 +.6 +.6
b = .5 +.4 +.2
самые большие камни.
в обоих случаях будет выполняться условие.
Насчет доказательства не знаю по моему все ок,тем более что это натуральный алгоритм, а не математика. Если сильно надо почитай книжку о множествах и последовательностях - ничего сложного но полезно. Может - это и зря было сказано, не знаю.
neondartal@yandex.ru если надо
ответить могу не сразу
  #3  
Старый 07.10.2008, 18:19
гость

 
Сообщений: n/a

Допустим камни весом от 0 до 1. А теперь теперь возьми кучу с максимальным весом камней
к примеру c = {1,1,1,1,1,1,1,1}.
А теперь возьми две кучи a и b.
Теперь кидай в каждую кучу камни, сравнивая в какой меньше - туда и кидаем. Посуди сам в этом случае кучи примерно будут равны. Одна пытается догнать другую.При этом разница между ними будет будет 1 ;
тем более отношение - заведомо <=1 (меньшая/большую). Заметь, если взять кучу с большим числом камней то отношение будет стремиться к 1
или равно ему Проверь сам - возьми 10000 камней (a/b = 1) , 10001 камень (a/b~0.9999999). Теперь возьми небольшую кучу с камнями от 0 до 1. Заметь разница между ними по-прежнему не может быть больше 1;
И небольше самого большого камня в общей куче незавимимо от того в каком месте кучи он стоит. Это потому что, ты положил самый большой камень например в кучу a , то куча b будет плюсовать к себе дальнейшие
камни пока не перегонит a, НО! разница между кучами не будет больше
веса самого большого камня.(потом кучи пытаются догнать друг друга и камней побольше самого бол. -нет) Проверь сам.
Сам подумай, если камни от 0 до 1, то разница между кучами ними <=1.
Отношение между кучами будет разное в зависимости от того где сам. б. камень лежит в куче.
Вот о вопросе о том почему самый большой камень нужен вначале.
Опять просто возьми кучу из 3 камней с{1,1,1}.Смотри,
самый большой получился =1,

куча а = 1
куча b = 1+1 или наоборот

это минимум камней при котором условие выполняется с максимальным весом !!! обрати внимание.
отношение между кучами = 0.5 или 2 не больше,
если в общей куче увеличить кол-во камней то отношение будет меняться в сторону 1. a/b = 0.5 максимум отношения.
теперь если оставить камень max=1. а остальные <1 то , занеся 1 в кучу a , потом будешь заносить в кучу b пока она не перегонит a. потом наоборот итд итп.
вариант с кучей {1,1,1} является максимальным по этому поводу:
минимальное кол-во камней при котором a/b =0.5 и камни по весу максимальны.
Теперь куча{0.1,0.6,1, 0.4,0.4} . Сам.б. = 1;
1:
a = 1
b = 0.1+0.6+0.4 =1.1
2:
a = 1+0.4 = 1.4;
b = 1.1

a/b <=0.5;

Сам.б. камень положен первым , тогда другая куча сначала догоняет первую пока не пергонит, потом у них отношение будет <0.5. единственный вариант когда отношение будет = 0.5 - читай выше.
Я не учитываю условия когда в одной куче 1 а в другой 0.4 , это уже сам учтешь.
Если ты хочешь чтобы у тебя было отношение = 3/2.
максимум: с {1,1,1,1,1}. ты ложишь один сам.б. камень в одну кучу, два последующих сам. больщих в другую.
вот.

a = 1 +1
b = 1+1 +1
это минимум камней при котором условие выполняется с максимальным весом !!!

a/b = 2/3 или b/2 = 3/2 = 1.5 раза, тогда взяв меньшие веса в куче b/a<1.5

если надо наложи в кучи сначала столько 1 чтобы их отношение = m/n
m - колво макс. камней в первой
т - во второй или наоборот.

С весами меньшими все также. все будет работать.
Только еслу нужно определенное отношение просто накидай в уме в обе кучи столько камней с максимальным весом чтобы их отношение было тем которое нужно.

например
3/5

a = 1+1+1;
b = 1+1+1+1+1;
это максим.веса.

а = .8 +.6 +.6
b = .5 +.4 +.2
самые большие камни.
в обоих случаях будет выполняться условие.
Насчет доказательства не знаю по моему все ок,тем более что это натуральный алгоритм, а не математика. Если сильно надо почитай книжку о множествах и последовательностях - ничего сложного но полезно. Может - это и зря было сказано, не знаю.
neondartal@yandex.ru если надо
ответить могу не сразу
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
бинарный посик - помогите разобраться Димка Сортировка и поиск 12 06.01.2011 14:36
Помогите с задачей, пожалуйста! Alexey Математические алгоритмы (другое) 1 18.09.2008 15:51
Помогите пожалуйста с задачей! гость Математические алгоритмы (другое) 5 13.12.2007 00:34
Помогите с задачей,оч надо!О комивояжоре Светлана Математические алгоритмы (другое) 1 07.12.2007 08:45
помогите разобраться Мёртвый Анархист Реализация, исходники, языки 13 23.01.2007 08:25