1. Даны 2 буфера фиксированной длины. В начале каждого лежат данные (строчки текст), дальне до конца нули. Поменять строчки местами и перевернуть их задом на перед, так, чтобы в итоге нули опять находились в конце, а текст — в начале. (Microsoft)
2a. Два игрока играют по очереди называют число, достоинство воображаемой разменной монеты. При этом нужно, чтобы это число нельзя было выплатить при помощи ранее называнных монет. Проигрывает назвавший число 1. Доказать, что игра не может продолжаться бесконечно. (J.H.Conway)
2b. Если у нас уже есть монеты достоинствами x[0]...x[n] (каждого типа — неограниченнок количество), то можно задать вопрос: как нам выплатить данную сумму денег S минимальным общим числом монет? Напишите соответвующую программу.
3. Может ли цепная реакция в gridgame продолжаться бесконечно?
(Mark James)
4. Что делает следующий С++ код? (Matt Marcus)
struct A {
A(const volatile void*);
};
char f(A);
int f(...);
template
struct Test {
static const int value = (sizeof(f(*(T*)0)) == sizeof(char));
};
5а. Вы сидите в лодке, плавающей посреди небольшого озера. У Вас собой на борту есть большой кирпич. Если выкинуть его в озеро, уровень воды увеличится? уменьшится? останется неизменным? (популярный вопрос, на многих фирмах задают, в том числе на и Микрософте)
5b. Кусок замороженного спирта в бочке с пивом. Что станет с уровнем жидкости, когда спирт весь растает? (не понмню откуда)
6. Вы отправились в прошлое на машине времени и повстречали, ну скажем, Михайло Ломоносова (варианты: А.С. Пушкина, Томаса Эдисона, Николу Теслу итп). Объясните ему, что такое "Интернет" (мое, по Микрософтовской идее). (Садистский вариант: объясните ему, что такое General Protection Failure
7. У вас есть 8 с виду одинаковых монет, одна из которых, тем не менее, фальшивая. Фальшивая монета чуть тяжелее, но во всем остальном идентична настоящим. У вас также есть, в лучших традициях жанра, весы с чашечками, как у богини правосудия. За какое минимальное число взвешиваний можно определить фальшивку? (популярная задача)
8. Придумайте структуру данных, которую бы мог на выходе создать парсер MAKE-файлов. Напишите (на псевдокоде) интерпретатор/исполнитель для этой структуры (Microsoft)
9. Протестируйте Save Dialog в Notepad'e (задача для микософтовских тестеров)
10. Есть три урны из тех, что содержат шары в задачках по теории вероятности. На первой написано "ЧЕРНЫЕ", на второй — "БЕЛЫЕ", на третьей — "ЧЕРНЫЕ И БЕЛЫЕ". В одной лежат белые шары, в другой — черные, в оставшейся — и черные и белые. Все надписи заведомо ложны. Разрешается достать один шар из только одной урны. Как определить в какой урне что лежит? (Microsoft)
11. Дано много картинок в формате RGB (т.е. цвет каждого пикселя представлен тремя числами: количеством красного цвета, зеленого цвета и синего цвета). Перевести картинки в 256-цветовой формат (а-ля Gif) с использованием заданной палитры (палитра одна на все картинки). Т.е. вместо каждого цвета подставить индекс ближайшего к нему цвета в палитре. Разумеется, хорошо бы это сделать как можно более эффективно. (Google)
12. Обойти двоичное дерево, НЕ используя рекурсию. (Michael Abrash)
13. На консоли Xbox адрес пикселя с координатами x, y записывается в двоичной форме как x7 y7 x6 y6 x5 y5 x5 y5 x4 y4 x3 y3 x2 y2 x1 y1 x0 y0 (где xn, yn — соответствующие биты чисел x и y). Дан пиксель с адресом a, найти адрес его соседа справа (Visual Concepts)
14. Дана строчка текста, переставить в ней все слова в противоположном порядке, так чтобы, например, строчка "Здесь был Вася" превратилась в "Вася был Здесь". Дополнительную память выделять не разрешается (популярная задача)
15. Дано число. Определить, является ли оно целой степенью 2. (Microsoft и другие)
16а. Дан связный список. Проверить, нет ли в нем циклов. (популярная)
16b. Сделать то же самое с двоичным деревом.
17. В вершинах равностороннего треугольника со стороной 200 метров сидит по собаке. По команде "старт!" каждая из них начинает гнаться за своей соседкой слева со скоростью 200 метров в минуту. Каждая собака бежит точно в направлении текущего положения своей (тоже, разумеется, бегущей) цели. Поэтому их траектории представляют некие сходящиеся спирали. Через какое время все собаки сойдутся, (вернее, сбегутся) в центре? (вариант популярной задачи)
18. Даны две строчки битов, длинная и короткая. Определить, как можно более эффективно, содержится ли короткая строчка в длинной (мое)
19. Почему пивные банки скошены сверху и снизу? (Microsoft)
20. Как провести электричество, чтобы свет на лестнице можно было включать/выключать и с верхней площадки, и с нижней. Нарисуйте схему проводки.
21. Даны указатели на два элемента в двоичном дереве, найти их общего родителя (Microsoft)
22. Стандартный способ "честного" деления пирога: первый участник делит, второй выбирает себе один из кусков, оставшийся кусок достается первому. Что делать если участников 3? (Мартин Гарднер, чтоли?)
23. Есть круглый бассейн. От его бортика в направлении точно на север отплыла рыба. Проплыв 6 метров, она опять столкнулась с бортиком. Тогда рыба повернула на восток, проплыла еще 8 метров и опять столкнулась с бортиком. Найти диаметр бассейна. (опять Мартин Гарднер)
24. Дано число int x. Как наиболее эффективно подсчитать количество единичных битов в нем, если нельзя пользоваться дополнительной памятью. Соответствующей командой ассемблера тоже пользоваться нельзя. (впервые видел в Dr.Dobbs Journal)
25. У вас есть зажигалка и веревка. Если веревку поджечь с конца, то она вся сгорит за полчаса. Как отмерить, при помощи этих двух предметов 15 минут? Важное обстоятельство: Веревка горит неравномерно, где-то быстрее, где-то медленнее. (очень популярная задача)
26. Есть программа, которая рисует на экране шар (скажем, с картой Земли на поверхности). Хочется, чтобы можно было при помощи мыши управлять ориентацией шара, дабы рассмотреть его со всех сторон. Придумайте соответствующий пользовательский интерфейс. Напишите (на псевдокоде) основной алгоритм управления ориентацией. (мое)
27. Вы стоите посреди замерзшего озера на идеально скользком льду. Трения нет вообще. Придумайте как можно больше способов добраться до берега. (Physics Mountain)
28.a (Для мэнеджеров, наверное) Вы — добрый эльф, меткий стрелок из лука. За Вами гонится отряд из 10 орков, злах и эгоистичных тварей. К счастью, они пока далеко позади. К несчастью, через какое-то время они Вас догонят и съедят. К счастью у Вас есть стрелы, которыми Вы можете разить орков наповал. К еще большему счастью, на одного орка хватает одной стрелы и бьете Вы без промаха. К несчастью, у Вас имеется только 5 стрел. К еще большему несчастью, орки об этом знают. Как Вам спастись? (D.Friedman)
Update28.b Какие у орков могут быть контр-приемы?
29. В какие времена суток положение всех трех стрелок часов (часовой, минутной и секундной) совпадает? (не помню откуда)Разъяснение Часы механические, и стрелки двигаются с равномерной скоростью.
30. Почему в стандарте С++ не позволено по умолчанию преобразовывать char** в const char**? Напишите пример кода, где такое преобразование (если бы его разрешили) привело бы к ошибке. (С++ faq)
31. У Вас с другом есть прямоугольный торт, из которого какой-то гад, к сожалению, уже вырезал (и съел) прямоугольный кусок. Ориентация и положение вырезанного куска могут быть совершенно произвольными. Как вам с другом разделить оставшийся торт на две равные части? (Microsoft)
32. Как передвинуть гору Фудзи? (Microsoft)
Кто что решит пишите
(с) voffka
18.01.06 13:40: Перенесено из 'Коллеги, улыбнитесь'
Здравствуйте, Grammer, Вы писали: G>22. Стандартный способ "честного" деления пирога: первый участник делит, второй выбирает себе один из кусков, оставшийся кусок достается первому. Что делать если участников 3? (Мартин Гарднер, чтоли?)
Кстати, если не пирог, а сыпучее вещество, то можно "честно" делить на любое количество участников
Здравствуйте, Grammer, Вы писали:
G>1. Даны 2 буфера фиксированной длины. В начале каждого лежат данные (строчки текст), дальне до конца нули. Поменять строчки местами и перевернуть их задом на перед, так, чтобы в итоге нули опять находились в конце, а текст — в начале. (Microsoft)
Тупая задача вроже бы. Или я совсем тупой. Или нужно запретить использование буферных переменных и ассемблера, чтобы обязательно использовать некоторый(-е) из нулей, как буфер.
Думаю, примерно так: на входе
DS:[ESI] и DS:[EDI] — буферы (первый эл-т)
inv1 proc near
CLD
PUSH EDI ; Кажетcя именно он в SCAS, а не ESI, но могу ошибаться
POP EBX
MOV AL, 0
REPNZ SCASB
PUSH EDI
DEC EDI
STD
@@sw: MOV AL, [EDI]
XCHG AL, [EBX]
STOSB
INC EBX
CMB EDI, EBX
JA @@sw
POP ECX
POP EDI
SUB ECX, EDI
RET
inv1 endp
bufswap proc
PUSH EDI
CALL inv1
MOV EDI, ESI
MOV EDX, ECX
CALL inv1
POP EDI
CMP EDX, ECX ; тут можно бы наверное CMPXCHG - но я остановился на i386 :)
JBE @@1
MOV ECX, EDX
@@1: CLD
@@2: MOV AL, [EDI]
XCHG AL, [ESI]
STOSB
INC ESI
LOOP ECX
RET
bufswap endp
Здравствуйте, Grammer, Вы писали:
G>17. В вершинах равностороннего треугольника со стороной 200 метров сидит по собаке. По команде "старт!" каждая из них начинает гнаться за своей соседкой слева со скоростью 200 метров в минуту. Каждая собака бежит точно в направлении текущего положения своей (тоже, разумеется, бегущей) цели. Поэтому их траектории представляют некие сходящиеся спирали. Через какое время все собаки сойдутся, (вернее, сбегутся) в центре? (вариант популярной задачи)
Забавная задача. Как правило ее легко решают школьники и студенты старших курсов. Первые, правда, предоставляют более красивое и изящное решение. А вот для студентов первых курсов эта задача оказывается не по зубам
Здравствуйте, Grammer, Вы писали:
G>2a. Два игрока играют по очереди называют число, достоинство воображаемой разменной монеты. При этом нужно, чтобы это число нельзя было выплатить при помощи ранее называнных монет. Проигрывает назвавший число 1. Доказать, что игра не может продолжаться бесконечно. (J.H.Conway)
Здравствуйте, MaximVK, Вы писали:
MVK>Забавная задача. Как правило ее легко решают школьники и студенты старших курсов. Первые, правда, предоставляют более красивое и изящное решение. А вот для студентов первых курсов эта задача оказывается не по зубам
А разве у нее есть какое-нибудь нормальное решение кроме перехода в неинерциальную систему координат, связанную с бегущей собакой?
Здравствуйте, VsevolodC, Вы писали:
VC>Очевидно, выигрывает первый игрок, назвав 0
И как с помощью 0 чего-нибудь кроме 0 выплачивать? Решение следует, очевидно, из того, что для взаимнопростых a,b любое с > 2*a*b можно представить в виде c = ax+by, где x и y >= 0.
Здравствуйте, Grammer, Вы писали:
G>1. Даны 2 буфера фиксированной длины. В начале каждого лежат данные (строчки текст), дальне до конца нули. Поменять строчки местами и перевернуть их задом на перед, так, чтобы в итоге нули опять находились в конце, а текст — в начале. (Microsoft)
Тупое решение состоит в том, чтобы сперва реверсировать каждую строчку, а затем обменять их (или наоборот: сперва обменять, а потом реверсировать).
Думаю, что оно будет и наиболее быстрым.
Хитрое решение отрабатывает цепочки обменов для каждой буквы по отдельности. Причём цепочки могут быть довольно длинными (предположительно, максимум достигается, если длины строк — соседние числа Фибоначчи; впрочем, это только догадка).
G>3. Может ли цепная реакция в gridgame продолжаться бесконечно? G>(Mark James)
G>struct A {
G>A(const volatile void*);
G>};
G>char f(A);
G>int f(...);
G>template// во-первых, даёт ошибку компиляции
G>struct Test {
G>static const int value = (sizeof(f(*(T*)0)) == sizeof(char)); // во-вторых, проверяет дизъюнкцию условий
// sizeof(int)==sizeof(char)
// T==A
// T - класс и существует T::operator A()
// T==U* (cv-квалификация типа U не имеет значения)
G>};
G>5а. Вы сидите в лодке, плавающей посреди небольшого озера. У Вас собой на борту есть большой кирпич. Если выкинуть его в озеро, уровень воды увеличится? уменьшится? останется неизменным? (популярный вопрос, на многих фирмах задают, в том числе на и Микрософте)
Не изменится. Водоизмещение пары лодка+кирпич не зависит от занимаемого ими объёма.
Хотя, если кирпич пористый или из замороженного спирта, то возможны варианты.
G>5b. Кусок замороженного спирта в бочке с пивом. Что станет с уровнем жидкости, когда спирт весь растает? (не понмню откуда)
Объём тающего спирта увеличивается, а объём охлаждаемой воды — уменьшается (до 4°С), затем снова увеличивается.
Объём водно-спиртовой смеси — меньше объёмов каждого из компонентов.
При растворении спирта выделяется тепло.
Бочка может быть термостабилизированной или термоизолированной. Колебания объёма могут быть изобарическими или сопровождаться колебаниями давления. При этом может затрачиваться разное количество энергии (одно дело пробулькать водяной затвор, другое — деформировать бочку, третье — сатурация или десатурация пива углекислым газом).
В общем, идёт довольно затейливый процесс, суммарный эффект варьируется и от количества веществ, и от начальной температуры, и от других условий.
G>6. Вы отправились в прошлое на машине времени и повстречали, ну скажем, Михайло Ломоносова (варианты: А.С. Пушкина, Томаса Эдисона, Николу Теслу итп). Объясните ему, что такое "Интернет" (мое, по Микрософтовской идее). (Садистский вариант: объясните ему, что такое General Protection Failure
Ну про GPF всё просто. Напился, ошибся дверью, хозяин набил морду.
G>12. Обойти двоичное дерево, НЕ используя рекурсию. (Michael Abrash)
А какой порядок обхода имеется в виду?
Если в глубину, то семейство обходов PLR, LPR, LRP (Parent, Left, Right) основываются на одном и том же алгоритме обхода. http://www.rsdn.ru/File/4783/traverse-bin-trees.gif
Если в ширину, то можно без рекурсии, но со счётчиком (и с квадратичным временем работы).
Здравствуйте, andyJB, Вы писали:
JB>Здравствуйте, VsevolodC, Вы писали:
VC>>Очевидно, выигрывает первый игрок, назвав 0 JB>И как с помощью 0 чего-нибудь кроме 0 выплачивать? Решение следует, очевидно, из того, что для взаимнопростых a,b любое с > 2*a*b можно представить в виде c = ax+by, где x и y >= 0.
Условие было только одно:
При этом нужно, чтобы это число нельзя было выплатить при помощи ранее называнных монет.
и оно выполняется, потому что ранее названных нет.
К>Тупое решение состоит в том, чтобы сперва реверсировать каждую строчку, а затем обменять их (или наоборот: сперва обменять, а потом реверсировать). К>Думаю, что оно будет и наиболее быстрым.
К>Хитрое решение отрабатывает цепочки обменов для каждой буквы по отдельности. Причём цепочки могут быть довольно длинными (предположительно, максимум достигается, если длины строк — соседние числа Фибоначчи; впрочем, это только догадка).
Что значит для каждой буквы по отдельности ?
Хитрое так примерно: (я пасквилятник, но надеюсь все же тут ошибиться негде почти).
void Reverse (char * const seq1, char * const seq2)
{ int len1, len2; char * ptr1, * ptr2; char buffer;
char * shorter_src, * shorter_dest, * longer; int len;
for( len1=0, ptr1 = seq1; *ptr1; ptr1++, len1++);
for( len2=0, ptr2 = seq2; *ptr2; ptr2++, len2++);
if ( len1 > len2)
{ len = len1; longer = ptr1; shorter_src = ptr2;
shorter_dest = seq2 + len1;
assert( shorter_src == seq2 + len2); } else
{ len = len2; longer = ptr2; shorter_src = ptr1;
shorter_dest = seq1 + len2;
assert( shorter_src == seq1 + len1); }
//Тонкость, если len1==len2, то shorter_src == shorter_dest и нужен промеж. буфер
// если нет, то и пофигу, буффер будет в регистре.while (len--) {
buffer = * (--shorter_src);
* (--shorter_dest) = * (--longer);
* longer = buffer;
}
}
Здравствуйте, Кодт, Вы писали:
G>>5а. Вы сидите в лодке, плавающей посреди небольшого озера. У Вас собой на борту есть большой кирпич. Если выкинуть его в озеро, уровень воды увеличится? уменьшится? останется неизменным? (популярный вопрос, на многих фирмах задают, в том числе на и Микрософте)
К>Не изменится. Водоизмещение пары лодка+кирпич не зависит от занимаемого ими объёма.
Уменьшится. Все-таки плотность кирпича больше плотности воды, поэтому будучи в лодке, он вытеснит больше воды, чем сам, пойдя ко дну. Исключения типа водоплавающих кирпичей пока не рассматриваем
Здравствуйте, Grammer, Вы писали:
G>7. У вас есть 8 с виду одинаковых монет, одна из которых, тем не менее, фальшивая. Фальшивая монета чуть тяжелее, но во всем остальном идентична настоящим. У вас также есть, в лучших традициях жанра, весы с чашечками, как у богини правосудия. За какое минимальное число взвешиваний можно определить фальшивку? (популярная задача)
2 достаточно. можно и с 9ю монетами справиться.
G>13. На консоли Xbox адрес пикселя с координатами x, y записывается в двоичной форме как x7 y7 x6 y6 x5 y5 x5 y5 x4 y4 x3 y3 x2 y2 x1 y1 x0 y0 (где xn, yn — соответствующие биты чисел x и y). Дан пиксель с адресом a, найти адрес его соседа справа (Visual Concepts)
P — точка.
сосед справа (( P | 1010101010101010 ) + 2) & ( P | 0101010101010101 )
G>Кто что решит пишите
G>(с) voffka
Здравствуйте, Аноним, Вы писали:
К>>Не изменится. Водоизмещение пары лодка+кирпич не зависит от занимаемого ими объёма.
А>Уменьшится. Все-таки плотность кирпича больше плотности воды, поэтому будучи в лодке, он вытеснит больше воды, чем сам, пойдя ко дну. Исключения типа водоплавающих кирпичей пока не рассматриваем
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, Grammer, Вы писали:
G>>1. Даны 2 буфера фиксированной длины. В начале каждого лежат данные (строчки текст), дальне до конца нули. Поменять строчки местами и перевернуть их задом на перед, так, чтобы в итоге нули опять находились в конце, а текст — в начале. (Microsoft)
К>Тупое решение состоит в том, чтобы сперва реверсировать каждую строчку, а затем обменять их (или наоборот: сперва обменять, а потом реверсировать). К>Думаю, что оно будет и наиболее быстрым.
Обмен с реверсом одновременно, но с получением нулей вначале.
a[N1], b[N2] — длины буферов, пусть N=min(N1,N2). Начинаем менять пары местами a[0]<->b[N-1], a[1]<->b[N-2] и т.д. Получаем строки с нулями вначале — циклически сдвигаем их в начало.
G>>4. Что делает следующий С++ код? (Matt Marcus) К>
К> // T==U* (cv-квалификация типа U не имеет значения)Это что такое?
К>
G>>5а. Вы сидите в лодке, плавающей посреди небольшого озера. У Вас собой на борту есть большой кирпич. Если выкинуть его в озеро, уровень воды увеличится? уменьшится? останется неизменным? (популярный вопрос, на многих фирмах задают, в том числе на и Микрософте)
К>Не изменится. Водоизмещение пары лодка+кирпич не зависит от занимаемого ими объёма. К>Хотя, если кирпич пористый или из замороженного спирта, то возможны варианты.
Уменьшится. Пока кирпич в лодке он вытесняет воду объемом, равному своему весу. Когда кирпич падает в воду, он вытесняет воду объемом, равному своему объему. Посколько плотность кирпича явно больше плотности воды, во втором случае вытесняемой воды будет меньше.
К>Ну про GPF всё просто. Напился, ошибся дверью, хозяин набил морду.
Вы сидите за старинным столом, и пишете на листках, которую я даю, и по моей команде. Рядом стоит страж, который следит, чтобы стол не испачкали, и в случае чего бьет по голове дубиной. В какой-то момент я забываю дать листок, но даю команду что-то написать...
Здравствуйте, VsevolodC, Вы писали:
VC>и оно выполняется, потому что ранее названных нет.
И что? Второй назовет произвольное число, отличное от 1, и игра продолжится.
Здравствуйте, Grammer, Вы писали:
G>10. Есть три урны из тех, что содержат шары в задачках по теории вероятности. На первой написано "ЧЕРНЫЕ", на второй — "БЕЛЫЕ", на третьей — "ЧЕРНЫЕ И БЕЛЫЕ". В одной лежат белые шары, в другой — черные, в оставшейся — и черные и белые. Все надписи заведомо ложны. Разрешается достать один шар из только одной урны. Как определить в какой урне что лежит? (Microsoft)
Поскольку все три надписи ложные, надо их все поменять.
Есть только два варианта смены надписей
ЧБ
/ \
Ч----Б
по часовой стрелке и против.
Вытаскиваем из ЧБ один шар. Посколько надпись ложная, то в этой урне должны быть или все белые, или все черные. Смотрим на вытащенный шар, и двигаем надписи в соответствующем направлении.
Здравствуйте, andyJB, Вы писали:
JB>Здравствуйте, MaximVK, Вы писали:
MVK>>Забавная задача. Как правило ее легко решают школьники и студенты старших курсов. Первые, правда, предоставляют более красивое и изящное решение. А вот для студентов первых курсов эта задача оказывается не по зубам JB>А разве у нее есть какое-нибудь нормальное решение кроме перехода в неинерциальную систему координат, связанную с бегущей собакой?
Значит так:
1. Собака из точки A, бежит под 200 метров в минуту
2. Собака из точки B, с такой же скоростью.
3. Проекция скорости собаки B на AB, будет составлять sin(30) * 200 метров в минуту = 100 метров в минуту, причем на стречу собаки A.
4. Скорось приближения собак из точек A и B 200 + 100 = 300 метров в секунду.
5. Скорость сблищения не меняется, так как пробегая принибрижительно малое время не меняется отностительное взаимное положение собак, так как вновь образуется треугольник чуть меньших размеров с начальными данными по двидению собак.
Ну и собственно время: 200/300 = 2/3 минуты = 40 секунд.
P.S.: Еслиб был квадрат, то там проще, проекция собаки на ось AB =0, то есть, движением ее не учитываем и получаем 1 минутую
Здравствуйте, andyJB, Вы писали:
JB>Здравствуйте, VsevolodC, Вы писали:
VC>>и оно выполняется, потому что ранее названных нет. JB>И что? Второй назовет произвольное число, отличное от 1, и игра продолжится.
Действительно, не сообразил. Однако можно первым назвать -1.
G>23. Есть круглый бассейн. От его бортика в направлении точно на север отплыла рыба. Проплыв 6 метров, она опять столкнулась с бортиком. Тогда рыба повернула на восток, проплыла еще 8 метров и опять столкнулась с бортиком. Найти диаметр бассейна. (опять Мартин Гарднер)
Ответ: 10 метров, так как прямой угол всегда лежит на диамттре, теорема из школьного курса геометрии.
Здравствуйте, Grammer, Вы писали:
G>16а. Дан связный список. Проверить, нет ли в нем циклов. (популярная) G>16b. Сделать то же самое с двоичным деревом.
Здравствуйте, Аноним, Вы писали:
А>Ответ: 10 метров, так как прямой угол всегда лежит на диамттре, теорема из школьного курса геометрии.
Ну, поскольку на Земле нет рыб, которые умеют плавать точно в направлении сторон света, то дело, по-видимому, происходит на далекой планете. И тут все зависит от диаметра этой планеты. Геометрия на сфере, все таки, немного неевклидова...
Здравствуйте, Grammer, Вы писали:
G>18. Даны две строчки битов, длинная и короткая. Определить, как можно более эффективно, содержится ли короткая строчка в длинной (мое)
1) Нарезаем строчки на буквы (например, побайтно). Причём искомую нарезаем со всеми сдвигами. Естественно, появятся префиксы-постфиксы из неполных букв.
2) С помощью модифицированных алгоритмов КМП или БМ ищем вхождение всех (сдвинутых) буквенных строчек в искомой.
Если выжать все соки из КМП, это можно сделать очень эффективно, за один проход по тексту. А если из БМ — то ещё эффективнее (с перепрыгиванием).
Вопрос лишь в затратах на препроцессинг.
3) Для каждого найденного вхождения проверяем (с помощью маскирования) совпадение головного и хвостового огрызков.
B>3. Проекция скорости собаки B на AB, будет составлять sin(30) * 200 метров в минуту = 100 метров в минуту, причем на стречу собаки A. B>4. Скорось приближения собак из точек A и B 200 + 100 = 300 метров в секунду. B>5. Скорость сблищения не меняется, так как пробегая принибрижительно малое время не меняется отностительное взаимное положение собак, так как вновь образуется треугольник чуть меньших размеров с начальными данными по двидению собак.
Шикарно!
Вспоминается на ту же тему, но намного проще.
Дорого длинной, скажем, километр.
С одного конца идет девочка 3 км/ч.
С другого — мальчик-вылысыпыдыст, 7 км/ч.
У девочки есть собачка, она скучает дти рядом с человеком и убегает от девочки навстречу мальчику со скоростью 10 км/ч. Там ей становится скучно и она бежит обратно.
Вопрос — сколько километров намотает собачка.
Вот кстaти, ещё задачка. Делалась наспех, кое-как. Извиняйте. Опечатка в самом начале — имелся ввиду угол BA'O
Здравствуйте, Grammer, Вы писали:
G>31. У Вас с другом есть прямоугольный торт, из которого какой-то гад, к сожалению, уже вырезал (и съел) прямоугольный кусок. Ориентация и положение вырезанного куска могут быть совершенно произвольными. Как вам с другом разделить оставшийся торт на две равные части? (Microsoft)
Предполагаемое решение связано с пересечением множеств линий (или гиперплоскостей) честной бисекции целого торта и вырезанного из него куска, что в примитивном случае сводится к проведению прямой линии через центр торта и центр вырезанного куска.
Хитрое решение состоит в том, чтобы разрезать торт по горизонтали.
G>32. Как передвинуть гору Фудзи? (Microsoft)
Вырезать и скопировать на новом месте
"Группа умных альпинистов обошла гору Фудзи".
Здравствуйте, Arioch2, Вы писали:
A>Дорого длинной, скажем, километр. A>С одного конца идет девочка 3 км/ч. A>С другого — мальчик-вылысыпыдыст, 7 км/ч. A>У девочки есть собачка, она скучает дти рядом с человеком и убегает от девочки навстречу мальчику со скоростью 10 км/ч. Там ей становится скучно и она бежит обратно.
Да, это туфта. Вот другая задача, посложнее...
Из города в одном направлении выходят мальчик (М) и девочка (Д). М идет со скоростью 5 км/ч, Д идет со скоростью 3 км/ч. Вместе с ними выбежала собачка, которая бегает от М к Д и обратно. Скорость собачки 8 км/ч. В какой точке отрезка МД окажется собачка после 4 часа пути?
A>Вот кстaти, ещё задачка. Делалась наспех, кое-как. Извиняйте. Опечатка в самом начале — имелся ввиду угол BA'O A>
Картинка заблокирована проксей...
Здравствуйте, Spidola, Вы писали:
S>Здравствуйте, Grammer, Вы писали: G>>22. Стандартный способ "честного" деления пирога: первый участник делит, второй выбирает себе один из кусков, оставшийся кусок достается первому. Что делать если участников 3? (Мартин Гарднер, чтоли?)
S>Кстати, если не пирог, а сыпучее вещество, то можно "честно" делить на любое количество участников
Вообще-то "честный" это так:
Берётся палка колбасы. Режущий, медленно ведёт нож от края, ожидая команды от жаждущих колбаски. Тогда он останавливается, отрезает и отдаёт кусок тому, кто возжелал отрезать. Сам режущий так же может в любой момент остановиться и отрезать кусок себе, но в этом случае назначается новый режущий, из тех, кто ещё не получил своего.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Серёжа Новиков,
программист
Re[3]: Интересные задачки для программистов
От:
Аноним
Дата:
18.01.06 13:36
Оценка:
Здравствуйте, Xander Zerge, Вы писали:
XZ>Здравствуйте, Spidola, Вы писали:
S>>Здравствуйте, Grammer, Вы писали: G>>>22. Стандартный способ "честного" деления пирога: первый участник делит, второй выбирает себе один из кусков, оставшийся кусок достается первому. Что делать если участников 3? (Мартин Гарднер, чтоли?)
S>>Кстати, если не пирог, а сыпучее вещество, то можно "честно" делить на любое количество участников
XZ>Вообще-то "честный" это так: XZ>Берётся палка колбасы. Режущий, медленно ведёт нож от края, ожидая команды от жаждущих колбаски. Тогда он останавливается, отрезает и отдаёт кусок тому, кто возжелал отрезать. Сам режущий так же может в любой момент остановиться и отрезать кусок себе, но в этом случае назначается новый режущий, из тех, кто ещё не получил своего.
A>>Вот кстaти, ещё задачка. Делалась наспех, кое-как. Извиняйте. Опечатка в самом начале — имелся ввиду угол BA'O A>> RB>Картинка заблокирована проксей...
А сам сайт? там в папке еще исходник картинки для OpenOffice. Листинг папок включен.
B>3. Проекция скорости собаки B на AB, будет составлять sin(30) * 200 метров в минуту = 100 метров в минуту, причем на стречу собаки A. B>4. Скорось приближения собак из точек A и B 200 + 100 = 300 метров в секунду. B>5. Скорость сблищения не меняется, так как пробегая принибрижительно малое время не меняется отностительное взаимное положение собак, так как вновь образуется треугольник чуть меньших размеров с начальными данными по двидению собак.
Собственно, это и называется перейти в систему координат, связанную с одной из собак. В ней собака, за которой бежит данная, будет бежать навстречу со скоростью 300 м/мин. Вопрос, собственно, какое ещё решение можно придумать?
Кодт wrote: > G>32. Как передвинуть гору Фудзи? (Microsoft) > Вырезать и скопировать на новом месте
А еще можно использовать shallow copy — просто назвать другую гору
"Фудзи". Старую потом можно взорвать или перименовать
Здравствуйте, VsevolodC, Вы писали:
VC>Здравствуйте, Grammer, Вы писали:
достоинство воображаемой разменной монеты.
............
G>>При этом нужно, чтобы это число нельзя было выплатить при помощи ранее называнных монет. Проигрывает назвавший число 1. Доказать, что игра не может продолжаться бесконечно. (J.H.Conway)
Стою на асфальте я в лыжы обутый...
Или я читать разучился...
Здравствуйте, bedward70, Вы писали:
B>Здравствуйте, andyJB, Вы писали:
JB>>Здравствуйте, MaximVK, Вы писали:
MVK>>>Забавная задача. Как правило ее легко решают школьники и студенты старших курсов. Первые, правда, предоставляют более красивое и изящное решение. А вот для студентов первых курсов эта задача оказывается не по зубам JB>>А разве у нее есть какое-нибудь нормальное решение кроме перехода в неинерциальную систему координат, связанную с бегущей собакой?
B> B>3. Проекция скорости собаки B на AB, будет составлять sin(30) * 200 метров в минуту = 100 метров в минуту, причем на стречу собаки A.
А почему sin ? или я чего-то не понял ? BC это вроде через косинус будет
Здравствуйте, GSL, Вы писали:
GSL>Вот лог игры GSL>2, 3, 4, 6, 10..... бесконечность
Правильная формулировка: "при помощи любого количества монет ранее названных достоинств".
Здравствуйте, GSL, Вы писали:
GSL>Вот лог игры GSL>2, 3, 4, 6, 10..... бесконечность
Если бы каждую монету можно было использовать в сумме ровно по 1 разу, то любая супервозрастающая последовательность нас удовлетворила бы.
Например, степени 2.
Но фишка в том, что вводя очередную монету, мы предполагаем, что таких монет у нас неограниченное количество.
В твоём примере, ход "4" недопустим, поскольку 4=2+2.
Доказательство на пальцах:
Лемма (требует отдельного доказательства):
Имея набор M={m1,m2,...,mk}, мы можем получить любые суммы вида s = gcd(M)*(start(M)+k), где gcd — наибольший общий делитель, а start — некое стартовое значение множителя.
Разумеется, кроме этих сумм, мы можем получать и другие, но пока что рассмотрим только это.
Очевидно, что если M' = M+{m'}, то gcd(M')<=gcd(M), gcd(M')*start(M')<=gcd(M)*start(M) — то есть, добавляя новую монету, мы делаем решето более густым (уж точно — не менее густым).
Возьмём некоторый начальный набор M0. s0=start(M0), g0=gcd(M0).
Разобьём множество натуральных чисел на две части: V0 = [1..s0*g0], N0 = N\V0.
Предположим, что наша игра бесконечна. Это значит, что рано или поздно мы начнём делать ходы из N1. (Поскольку N0 конечно).
Теперь рассмотрим кольцо вычетов N mod g0. G0 = [0..g0-1]
Каждый ход в N1 должен быть не кратным g0, т.е. ему соответствует g = (m mod g0), g!=0.
Однако в этом случае корректируется НОД, g1 = gcd(g0,g), что приводит к сужению кольца: G1=[0..g1-1].
В конце концов, получим gt = 1, кольцо схлопнется — мы вычеркнем все элементы из N0.
После чего останемся с множеством V0, которое также исчерпаем.
Здравствуйте, andyJB, Вы писали:
JB>Здравствуйте, VsevolodC, Вы писали:
VC>>Очевидно, выигрывает первый игрок, назвав 0 JB>И как с помощью 0 чего-нибудь кроме 0 выплачивать?
Мне как-то показывали монету с цифрой "0" в номинале и какими-то надписями на арабском. Так что, все честно. Только нолик там был слегка кособокий.
Навскидку:
G> 2b. Если у нас уже есть монеты достоинствами x[0]...x[n] (каждого типа — неограниченнок количество), то можно задать вопрос: как нам выплатить данную сумму денег S минимальным общим числом монет? Напишите соответвующую программу.
Видимо необходимо разложить S = i0*x[0] + i1*x[1] + ... + in*x[n] так, чтобы сумма i0 + i1 + ... + in была минимальной.
Если есть монета достоинством 1 задача решается достаточно тривиально. А вот если такой монеты нет... Надо думать.
G> 7. У вас есть 8 с виду одинаковых монет, одна из которых, тем не менее, фальшивая. Фальшивая монета чуть тяжелее, но во всем остальном идентична настоящим. У вас также есть, в лучших традициях жанра, весы с чашечками, как у богини правосудия. За какое минимальное число взвешиваний можно определить фальшивку? (популярная задача)
1. Разделить монеты на две равные кучки.
2. Сравнить вес кучек, в более легкой — все монеты настоящие.
3. Повторять для более тяжелой кучки, пока не останется одна тяжелая монета.
Т. о. минимальное число взвешиваний — логарифм по основанию 2 от исходного кол-ва монет. Для 8 монет: 3 взвешивания.
G> 10. Есть три урны из тех, что содержат шары в задачках по теории вероятности. На первой написано "ЧЕРНЫЕ", на второй — "БЕЛЫЕ", на третьей — "ЧЕРНЫЕ И БЕЛЫЕ". В одной лежат белые шары, в другой — черные, в оставшейся — и черные и белые. Все надписи заведомо ложны. Разрешается достать один шар из только одной урны. Как определить в какой урне что лежит? (Microsoft)
Достаем шарик из "ЧЕРНЫЕ И БЕЛЫЕ".
Если он черный:
в 3-й корзине черные шарики;
в 1-й корзине белые шарики;
во 2-й корзине черные и белые шарики.
Если он белый:
в 3-й корзине белые шарики;
во 2-й корзине черные шарики;
в 1-й корзине черные и белые шарики.
G> 23. Есть круглый бассейн. От его бортика в направлении точно на север отплыла рыба. Проплыв 6 метров, она опять столкнулась с бортиком. Тогда рыба повернула на восток, проплыла еще 8 метров и опять столкнулась с бортиком. Найти диаметр бассейна. (опять Мартин Гарднер)
То есть в круг должен вписываться прямоугольник 6x8. Тогда диаметр бассейна — диагональ прямоугольника.
По т. Пифагора D = sqrt(6*6 + 8*8) = 10 метров.
G> 27. Вы стоите посреди замерзшего озера на идеально скользком льду. Трения нет вообще. Придумайте как можно больше способов добраться до берега. (Physics Mountain)
1. Разнообразные варианты реактивного движения: кидать вещи, дуть и т.д. в противоположном требуемому направлении.
2. Поорать в противоложном направлении — звуковые волны отразятся от противоположного берега и подтолкнут в нужном направлении
3. Аналогично со светом.
G> 29. В какие времена суток положение всех трех стрелок часов (часовой, минутной и секундной) совпадает? (не помню откуда)Разъяснение Часы механические, и стрелки двигаются с равномерной скоростью.
Здравствуйте, Fedor Novikov, Вы писали:
FN>Мне как-то показывали монету с цифрой "0" в номинале и какими-то надписями на арабском. Так что, все честно. Только нолик там был слегка кособокий.
Ага. Это их 5 копеек.
Здравствуйте, andyJB, Вы писали:
JB>Здравствуйте, GSL, Вы писали:
GSL>>Вот лог игры GSL>>2, 3, 4, 6, 10..... бесконечность JB>Правильная формулировка: "при помощи любого количества монет ранее названных достоинств".
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, GSL, Вы писали:
GSL>>Вот лог игры GSL>>2, 3, 4, 6, 10..... бесконечность
К>Если бы каждую монету можно было использовать в сумме ровно по 1 разу, то любая супервозрастающая последовательность нас удовлетворила бы. К>Например, степени 2.
К>Но фишка в том, что вводя очередную монету, мы предполагаем, что таких монет у нас неограниченное количество. К>В твоём примере, ход "4" недопустим, поскольку 4=2+2.
К>Доказательство на пальцах:
К>Лемма (требует отдельного доказательства): К>Имея набор M={m1,m2,...,mk}, мы можем получить любые суммы вида s = gcd(M)*(start(M)+k), где gcd — наибольший общий делитель, а start — некое стартовое значение множителя.
К>Разумеется, кроме этих сумм, мы можем получать и другие, но пока что рассмотрим только это.
К>Очевидно, что если M' = M+{m'}, то gcd(M')<=gcd(M), gcd(M')*start(M')<=gcd(M)*start(M) — то есть, добавляя новую монету, мы делаем решето более густым (уж точно — не менее густым).
К>Возьмём некоторый начальный набор M0. s0=start(M0), g0=gcd(M0). К>Разобьём множество натуральных чисел на две части: V0 = [1..s0*g0], N0 = N\V0.
К>Предположим, что наша игра бесконечна. Это значит, что рано или поздно мы начнём делать ходы из N1. (Поскольку N0 конечно).
К>Теперь рассмотрим кольцо вычетов N mod g0. G0 = [0..g0-1] К>Каждый ход в N1 должен быть не кратным g0, т.е. ему соответствует g = (m mod g0), g!=0. К>Однако в этом случае корректируется НОД, g1 = gcd(g0,g), что приводит к сужению кольца: G1=[0..g1-1].
К>В конце концов, получим gt = 1, кольцо схлопнется — мы вычеркнем все элементы из N0.
К>После чего останемся с множеством V0, которое также исчерпаем.
Я наверное уже просто давно не читал теории, и такие выкладки несколько сложны, но можно доказать и более чем просто....
Берем монетки от 2 и 3 не сложно показать что, их них можно набрать вот такие суммы
2, 3, 4, 5, 6, 7, 8, 9.....
Ну а теперь все тем, кто папался на такое доказательство предела игры
Просто распирает меня
Вообщем, то что я написал до этого
Это только говорит нам о том, что проиграет тот кто первым назовет 2 или 3 не более того.
Вопрос первоначальный, о доказательстве того что игра не бесконечна, несколько глуп. И вот почему.
Если рассматривать последовательность по вверхсходящей, то да игра не бесконечна( опять же 2 и 3 ). Однако, поробуем идти по низходящей ветке...например если начинать с 1000 то максимально имеем 1000 ходов
1000, 999, 998, 997
А если от бесконечности
бесконечность, бесконечность — 1, бесконечность — 2, ... ?
А что в конце ? А тут в зависимости от того от чего мы оттолкнемся, я бы предпочел от того что бесконечность — N = бесконечность. И у меня в конце бесконечность
Гораздо интереснее придумать тактику выгрыша, а тут надо точно иметь предел верхнего значения. Но скорее всего это будет алгоритм разделяй и властвуй только сильно адаптированный.
Здравствуйте, Grammer, Вы писали:
G>31. У Вас с другом есть прямоугольный торт, из которого какой-то гад, к сожалению, уже вырезал (и съел) прямоугольный кусок. Ориентация и положение вырезанного куска могут быть совершенно произвольными. Как вам с другом разделить оставшийся торт на две равные части? (Microsoft)
Разрезать по прямой, проходящей через центр симметрии торта и центр симметрии дыры.
Здравствуйте, GSL, Вы писали:
GSL>Здравствуйте, bedward70, Вы писали:
B>> B>>3. Проекция скорости собаки B на AB, будет составлять sin(30) * 200 метров в минуту = 100 метров в минуту, причем на стречу собаки A.
GSL>А почему sin ? или я чего-то не понял ? BC это вроде через косинус будет Я рассматрнивал верхний угол малого треугольника.
Но можно и прилежащий угол, соответственно COS(60) =0.5, что не повлияет на результат вычислений.
Здравствуйте, GSL, Вы писали:
GSL>Я наверное уже просто давно не читал теории, и такие выкладки несколько сложны, но можно доказать и более чем просто....
GSL>Берем монетки от 2 и 3 не сложно показать что, их них можно набрать вот такие суммы GSL>[b]Итого имеем не то, что ограниченное, имеем просто смехотворное количество монеток 2 и 3.
Естественно. Как только будут названы несколько чисел, у которых НОД = 1 — всё, игра стремительно близится к концу.
Моё доказательство основывалось на том, что через конечное число ходов приходится делать ход, заведомо некратный текущему НОДу — и, как следствие, уменьшающий итоговый НОД.
Почему "через конечное число ходов", а не "на следующий ход"?
Потому что могут быть ходы, кратные НОДу и не кратные ни одной из монет (например, меньшие, чем минимальная монета).
Теперь — доказательство леммы о том, что с помощью двух монет можно получить любые суммы, кратные их НОДу (начиная с некоего стартового значения).
Сперва сократим НОД (очевидно, что умножая/деля строго нацело, мы не меняем картину).
Итак: даны два взаимно простых числа p, q. Доказать, что с их помощью можно получить любые суммы, начиная с некоего стартового значения.
Рассмотрим кольцо по модулю q (пусть p<q).
Числа 0, p, 2p, 3p, ... (q-1)p mod q принимают разные значения, покрывая всё кольцо.
Пусть нам нужно найти разложение для произвольного числа x >= qp. Найдём k такое что x == kp mod q (очевидно, что оно найдётся, см.выше).
Тогда (x-kp)==0 mod q, то есть, (x-kp)==mq. m>=0, потому что x>=qp, а k<q.
Значит, по меньшей мере начиная с произведения (а, если подумать, то начиная с НОК) монет, разложимы все числа, кратные НОД.
Здравствуйте, bedward70, Вы писали:
B>Здравствуйте, GSL, Вы писали:
GSL>>Здравствуйте, bedward70, Вы писали:
B>>> B>>>3. Проекция скорости собаки B на AB, будет составлять sin(30) * 200 метров в минуту = 100 метров в минуту, причем на стречу собаки A.
GSL>>А почему sin ? или я чего-то не понял ? BC это вроде через косинус будет B> Я рассматрнивал верхний угол малого треугольника. B>Но можно и прилежащий угол, соответственно COS(60) =0.5, что не повлияет на результат вычислений.
Здравствуйте, Retran, Вы писали:
R>Привет!
R>Навскидку:
G>> 7. У вас есть 8 с виду одинаковых монет, одна из которых, тем не менее, фальшивая. Фальшивая монета чуть тяжелее, но во всем остальном идентична настоящим. У вас также есть, в лучших традициях жанра, весы с чашечками, как у богини правосудия. За какое минимальное число взвешиваний можно определить фальшивку? (популярная задача)
R>1. Разделить монеты на две равные кучки. R>2. Сравнить вес кучек, в более легкой — все монеты настоящие. R>3. Повторять для более тяжелой кучки, пока не останется одна тяжелая монета.
R>Т. о. минимальное число взвешиваний — логарифм по основанию 2 от исходного кол-ва монет. Для 8 монет: 3 взвешивания.
Если было бы 9 монет, то наверно решил бы правильно.
R>>Т. о. минимальное число взвешиваний — логарифм по основанию 2 от исходного кол-ва монет. Для 8 монет: 3 взвешивания.
G>Если было бы 9 монет, то наверно решил бы правильно.
Там хорошая подсказка — "тяжелее". Во тесли бы просто отличалась по весу — то тоже бы три было.
А так две
Что мы можем за одно взвешивание? сравнить монету с эталоном.
Т.е. если у нас есть эталон и две монеты (фальшивка + нормальная) — мы находим фальшивку.
8-2 = 6. 6 = 3+3.
Взвешиваем кучки по три монеты. Если они одинаковы — фальшивка не на весах и см. выше.
Если одна кучка тяжелее, то взвешиваем две монеты из кучки и смотри какая тяжелее.
Вот если бы неизвестно было тяжелее/легче, тогда упс
Здравствуйте, Аноним, Вы писали:
А>тема пирога не раскрыта
Очевидно, что переменная толщина колбасы на решение не влияет, если нож движется непрерывно.
Если уж очень хочется, то можно двигать нож со скорость обратно пропорциональной толщине.
Здравствуйте, andyJB, Вы писали:
JB>Вопрос, собственно, какое ещё решение можно придумать?
Проинтегрировать. Это наверное даже не так сложно (думать лень), но первокурсник может и не справиться, а это именно то, что должно придти ему в голову.
Здравствуйте, Grammer, Вы писали:
G>27. Вы стоите посреди замерзшего озера на идеально скользком льду. Трения нет вообще. Придумайте как можно больше способов добраться до берега. (Physics Mountain)
Высморкаться?...
Я, конечно, ничего в этом не понимаю,
но позвольте и мне высказаться!
Здравствуйте, Grammer, Вы писали:
G>6. Вы отправились в прошлое на машине времени и повстречали, ну скажем, Михайло Ломоносова (варианты: А.С. Пушкина, Томаса Эдисона, Николу Теслу итп). Объясните ему, что такое "Интернет"
Очень быстрый курьер.
G> (мое, по Микрософтовской идее). (Садистский вариант: объясните ему, что такое General Protection Failure
Открываете window и горшок с подоконника падает вам на ногу.
G>28.a (Для мэнеджеров, наверное) Вы — добрый эльф, меткий стрелок из лука. За Вами гонится отряд из 10 орков, злах и эгоистичных тварей. К счастью, они пока далеко позади. К несчастью, через какое-то время они Вас догонят и съедят. К счастью у Вас есть стрелы, которыми Вы можете разить орков наповал. К еще большему счастью, на одного орка хватает одной стрелы и бьете Вы без промаха. К несчастью, у Вас имеется только 5 стрел. К еще большему несчастью, орки об этом знают. Как Вам спастись? (D.Friedman)
Стрелять насквозь через двоих?
Заготовить ещё стрел?
Договориться?
Спрататься?
Замаскироваться? == Стать орком?
G>>28.a (Для мэнеджеров, наверное) Вы — добрый эльф, меткий стрелок из лука. За Вами гонится отряд из 10 орков, злах и эгоистичных тварей. К счастью, они пока далеко позади. К несчастью, через какое-то время они Вас догонят и съедят. К счастью у Вас есть стрелы, которыми Вы можете разить орков наповал. К еще большему счастью, на одного орка хватает одной стрелы и бьете Вы без промаха. К несчастью, у Вас имеется только 5 стрел. К еще большему несчастью, орки об этом знают. Как Вам спастись? (D.Friedman)
R3>Стрелять насквозь через двоих? R3>Заготовить ещё стрел?
Если они эгоситичные — м.б. пристрелить самого первого из них, и пусть они спорят, кто пойдёт первым ?
Нарисовать черту и пристредить кто переступит — и пусть спорят ?
Бегать по кругу и успевать доставать стрелы из трупов ?
Кстати, никто не сказал, а есть ли у него что-то кроме лука и стрел? С десяткой он не справится, но м.б. с пятёркой ?
Здравствуйте, Чай ник, Вы писали:
ЧН>Здравствуйте, Grammer, Вы писали:
G>>27. Вы стоите посреди замерзшего озера на идеально скользком льду. Трения нет вообще. Придумайте как можно больше способов добраться до берега. (Physics Mountain)
ЧН>Высморкаться?...
Медленно.
1) кинуть что-то ненужное в направлении противоположном нужному.
2) поднять голову вверх. вдохнуть. опустить голову в нормальное
положение, дунуть в направлении противоположном нужному.
Повторять до набора приемлимой скорости.
3) выполнять руками движения стиля плавания — кроль.
Но тут небольшое противоречие. В условии "трения нет вообще".
Вообще со льдом или вообще вообще?
Если есть трение с воздухом, то этот способ получится,
а 1) может не получиться (кончатся ненужные вещи .
4) плеваться в направлении противоположном нужному.
если трение об воздух есть, то непонятно, что раньше наступит —
обезвоживание или достижение цели.
5-)Хм... Ну в общем-то вроде бы есть два общих способа:
I) реактивный
II) взаимодействие с окружающей средой
Если трения об воздух нет, то 2-й отпадает.
Из "рукотворных" реактивных есть еще справление
естественных потребностей... Но возможно прийдётся подождать.
Можно еще реактивную струю своей кровищей обеспечить,
но уж лучше плеваться...
Если есть возможность заранее подготовится,
то возникает несколько дополнительных способов.
Например электромагнитное поле...
Или световое давление (очень мощный прожектор и большой белый/зеркальный парус).
Но долго...
Можно насыпать в точке destination гору. Гравитация нам поможет. Но очень долго.
Или очень большую.
Можно растопить лёд и вплавь...
Хм. Если ультрафиолетом светить и греть одну сторону,
какая-нить движущая сила возникнет?
Здравствуйте, rus blood, Вы писали:
RB>Из города в одном направлении выходят мальчик (М) и девочка (Д). М идет со скоростью 5 км/ч, Д идет со скоростью 3 км/ч. Вместе с ними выбежала собачка, которая бегает от М к Д и обратно. Скорость собачки 8 км/ч. В какой точке отрезка МД окажется собачка после 4 часа пути?
Сдается мне, собака может быть в любой точке и бежать в любом направлении. Во всяком случае, если повернуть время вспять, М, Д и собака в любом случае встретятся в исходной точке.
Здравствуйте, Багер, Вы писали:
Б>Насчёт задачки про два выключателя на одну лампочку.
Б>Решение, использующееся у меня на даче — один обыкновенный переключатель, один двойной.
Б>Есть другие решения?
Положение (1) выключателя включает фазу Ф, положение (2) фазу Ф+PI/2. Когда выключатели в одинаковых положениях разница фаз = 0.
Здравствуйте, Багер, Вы писали:
Б>Насчёт задачки про два выключателя на одну лампочку.
Б>Решение, использующееся у меня на даче — один обыкновенный переключатель, один двойной.
Б>Есть другие решения?
G>> 29. В какие времена суток положение всех трех стрелок часов (часовой, минутной и секундной) совпадает? (не помню откуда)Разъяснение Часы механические, и стрелки двигаются с равномерной скоростью.
R>В полдень и в полночь.
А в 13:05:05?
...Ei incumbit probatio, qui dicit, non qui negat...
Здравствуйте, vitaly_spb, Вы писали:
G>>> 29. В какие времена суток положение всех трех стрелок часов (часовой, минутной и секундной) совпадает? (не помню откуда)Разъяснение Часы механические, и стрелки двигаются с равномерной скоростью.
R>>В полдень и в полночь.
_>А в 13:05:05?
Часы механические, в них положение стрелок — непрерывные, а не ступенчатые функции времени.
В электромеханических — да, бывают такие варианты с дискретным перемещением каждой стрелки. И то, обычно часовая и минутная связаны одним шестерёночным механизмом, поэтому в 1:05 часовая будет примерно на 5.1/2 минутах.
Задачка про орков: сразу убиваем одного орка и бежит по кругу большого радиуса. Т.к. у нас осталось 4 стрел, то за нами погонятся минимум 5 орков. Значит остатся стеречь убитого орка могут остатся максимум 4 орка, которых мы убьем оставшимися стрелами после того как сделаем круг. Теперь подбираем стрелы и добиваем оставшихся 5 орков.
Про выключатели:обозначим
LB — состояние лампочки до переключения (0 — выкл, 1 — вкл)
A — состояние одного выключателя после переключения (0 — выкл, 1 — вкл)
B — состояние другого выключателя.
Нетрудно убедится что тогда состояние лампочки после выключения L равно:
L = (!LB && (A || B)) || (A && B && LB)
Схема построения отрицания, коньюнкции и дизьюнкции строится очевидным образом.
Останется только решить вопрос о том что надо как то ловить событие переключения и заставить схему реагировать только в момент переключения, иначе она начнет метатся между состояниями (LB = 0, A = 1, B = 0) и (LB = 1, A = 1, B = 0)
Про торт: первый делает надрез из середины торта к краю, а дальше двигает ножик по часовой стрелке от этого надреза и предлагает всем (в т.ч. и себе) взять кусочек. После того как кто нибудь заберет задача сводится к предыдущей с двумя лицами.
Здравствуйте, Serpenter, Вы писали:
S>Задачка про орков: сразу убиваем одного орка и бежит по кругу большого радиуса. Т.к. у нас осталось 4 стрел, то за нами погонятся минимум 5 орков. Значит остатся стеречь убитого орка могут остатся максимум 4 орка, которых мы убьем оставшимися стрелами после того как сделаем круг. Теперь подбираем стрелы и добиваем оставшихся 5 орков.
А если орки не останутся стеречь убитых товарищей, а просто вытащят стрелы и продолжат преследование?
А если они слишком тупые, чтобы подумать что мы можем забрать стрелы, то тогда надо убить сразу пятерых, а потом, вернувшись по кругу и вытащив стрелы, пристрелить оставшихся. Если убивать по одному, то даже самые тупые орки догадаются, что надо забрать стрелы.
Я больше склоняюсь к приводившемуся здесь варианту про линию, первый заступивший за которую получает стрелу в лоб, т.к. в условии сказано, что орки эгоистичные твари.
Ну, а если не сработает, то бежать по большому кругу и собирать стрелы
On Wed, 01 Feb 2006 19:46:41 +0300, vitaly_spb <19231@users.rsdn.ru> wrote:
> А>Уменьшится. Все-таки плотность кирпича больше плотности воды, поэтому > будучи в лодке, он вытеснит больше воды, чем сам, пойдя ко дну. > > А почему так можно поподробнее?
У куда подробнее ?
Плавающий предмет вытесняет воду равную своему весу. Утонувший — равную
своему объему.
Сравни сколько воды вытеснит плавающий и утонвший кирпич. Чем больше воды
вытеснено — тем выше уровень.
Здравствуйте, Grammer, Вы писали:
G>28.a (Для мэнеджеров, наверное) Вы — добрый эльф, меткий стрелок из лука. За Вами гонится отряд из 10 орков, злах и эгоистичных тварей. К счастью, они пока далеко позади. К несчастью, через какое-то время они Вас догонят и съедят. К счастью у Вас есть стрелы, которыми Вы можете разить орков наповал. К еще большему счастью, на одного орка хватает одной стрелы и бьете Вы без промаха. К несчастью, у Вас имеется только 5 стрел. К еще большему несчастью, орки об этом знают. Как Вам спастись? (D.Friedman) G>Update28.b Какие у орков могут быть контр-приемы?
Всё зависит от уровня интеллекта орков.
Вариант 1. Орки достаточно сообразительны для того, чтобы догадаться поднимать стрелы с трупов товарищей.
Тогда стратегия орков: бегут группой (все вместе) и если кого-то убьют — кто-то из живых поднимает стрелы с тела товарища (можно, например после этого их на всякий случай сломать или ещё как-нибудь уничтожить). Тем самым эльф не сможет получить уже использованные стрелы. Итог: как минимум 5 сытых орков
Вариант 2. Орки ужасно тупы. Тогда бегаем по какой-либо большой траектории, стреляем орков и собираем стрелы с их трупов. Итог: тупых орков стало на 10 меньше
G>32. Как передвинуть гору Фудзи? (Microsoft)
По формулировке задача очень похожа на так называемые задачи Ферми. Задачи, где не требуется точного ответа, а только лишь примерный (на глаз) ответ, причём способ их решения — прикинуть в уме, не используя калькулятор и пр.
Пример решения этой задачи:
Ну пусть требуется передвинуть Фудзи куда-то в другое место. Для этого используем японцев : т.е. пусть каждый японец отколет от горы камушек и перенесёт его в другое место. Пусть средняя масса (m) этого "камушка" — 1/2 кг. И пусть время (t), за которое один японец доберётся от места назначения до горы Фудзи и потом от горы до места назначения — 2 дня.
В 1996 году японцев было 125,6 млн. человек. Прикинем, что сейчас их будет (n) около 140млн = 14*10^7. Высота (h) Фудзиямы = 3776 м, возмём для краткости 3800м. Радиус основания горы (r) пусть будет километров 5. Ну и средняя плотность горных пород (p) пусть будет 10^4 кг/м^3.
Итак, массса горы Фудзи:
M = V*p = (1/3)*Pi*r^2*h*p ~ (1/3)*3*(5*10^3)^2*3800*10^4 = 25 * 10^10 * 3800 = 95 * 10^13 ~ 10^15 (кг).
Масса, которую перенесут японцы за 1 день
M_0 = m * n / t = (1/2) * 14*10^7 / 2 = 3.5 * 10^7 (кг);
Итого японцам понадобится:
M/M_0 = 10^15 / (3.5 * 10^7) ~ 3 * 10^7 (дней).
Это около 80 тысяч лет
Вывод: переносить горы вручную — плохая идея.
А если передвигать будут все люди Земли (n) ~ 6*10^9, m = 5, t = 1, то
M_0 = m * n / t = 3*10^10.
M/M_0 = (1/3) * 10^5 ~ 3*10^4 дней ~ 82 года.
The mind is not a vessel to be filled, it is a fire to be kindled. ((C) Plutarch)
<< RSDN@Home 1.2.0 alpha rev. 619>>
On Wed, 01 Feb 2006 19:46:41 +0300, vitaly_spb <19231@users.rsdn.ru> wrote:
> А>Уменьшится. Все-таки плотность кирпича больше плотности воды, поэтому > будучи в лодке, он вытеснит больше воды, чем сам, пойдя ко дну. > > А почему так можно поподробнее?
A куда подробнее ?
Плавающий предмет вытесняет воду равную своему весу. Утонувший — равную
своему объему.
Сравни сколько воды вытеснит плавающий и утонвший кирпич. Чем больше воды
вытеснено — тем выше уровень
--
Отправлено M2, революционной почтовой программой Opera: http://www.opera.com/mail/
Здравствуйте, Philip_PV, Вы писали:
P_P>Здравствуйте, Grammer, Вы писали:
G>>28.a (Для мэнеджеров, наверное) Вы — добрый эльф, меткий стрелок из лука. За Вами гонится отряд из 10 орков, злах и эгоистичных тварей.
P_P>Вариант 1. Орки достаточно сообразительны для того, чтобы догадаться поднимать стрелы с трупов товарищей. P_P>Тогда стратегия орков: бегут группой (все вместе) и если кого-то убьют — кто-то из живых поднимает стрелы с тела товарища (можно, например после этого их на всякий случай сломать или ещё как-нибудь уничтожить). Тем самым эльф не сможет получить уже использованные стрелы. Итог: как минимум 5 сытых орков
Вариант 1 отпадает. Т.к. сказано, что орки эгоистичны, следовательно, принцип "каждый сам за себя" лежит в основе их поведения. Пока один будет вытаскивать стрелу, другие сожрут эльфа и орк останется без еды. Стрелу может вытащить один орк, следоваетельно, другие не будут его ждать опять же в силу своей эгоистичности. Проблема когда останется два последних орка решается простым правилом — эльфу нельзя убивать предпоследнего орка пока у него не будет две или более стрел.
А вообще можно привести более строгое рассуждение в духе теории игр. Рассмотреть все возможные стратегии поведения орка и на основании их свойст смоделировать поведение.
Здравствуйте, olen33, Вы писали:
O>Я больше склоняюсь к приводившемуся здесь варианту про линию, первый заступивший за которую получает стрелу в лоб, т.к. в условии сказано, что орки эгоистичные твари.
Не прокатит. Как эгоистичные твари они вытолкнут по очереди пятерых своих товарищей за черту, а потом пойдут кушать эльфа.
Здравствуйте, MaximVK, Вы писали:
O>>Я больше склоняюсь к приводившемуся здесь варианту про линию, первый заступивший за которую получает стрелу в лоб, т.к. в условии сказано, что орки эгоистичные твари.
MVK>Не прокатит. Как эгоистичные твари они вытолкнут по очереди пятерых своих товарищей за черту, а потом пойдут кушать эльфа.
А решать, кого выталкивать, они будут методом жадных пиратов, которые делили 100 золотых монет?
Здравствуйте, Real 3L0, Вы писали:
R3>Здравствуйте, Philip_PV, Вы писали:
P_P>>... бегаем по какой-либо большой траектории ...
R3>Разве вообще можно убежать, если они быстрее тебя?
Расстояние будет сокращаться, вместе с численностью орков
В РПГ такое часто применяеться с разницей что ты просто убегаешь и отстреливаешься
Здравствуйте, olen33, Вы писали:
O>Здравствуйте, MaximVK, Вы писали:
O>>>Я больше склоняюсь к приводившемуся здесь варианту про линию, первый заступивший за которую получает стрелу в лоб, т.к. в условии сказано, что орки эгоистичные твари.
MVK>>Не прокатит. Как эгоистичные твари они вытолкнут по очереди пятерых своих товарищей за черту, а потом пойдут кушать эльфа.
O>А решать, кого выталкивать, они будут методом жадных пиратов, которые делили 100 золотых монет?
G>28.a (Для мэнеджеров, наверное) Вы — добрый эльф, меткий стрелок из лука. За Вами гонится отряд из 10 орков, злах и эгоистичных тварей. К счастью, они пока далеко позади. К несчастью, через какое-то время они Вас догонят и съедят. К счастью у Вас есть стрелы, которыми Вы можете разить орков наповал. К еще большему счастью, на одного орка хватает одной стрелы и бьете Вы без промаха. К несчастью, у Вас имеется только 5 стрел. К еще большему несчастью, орки об этом знают. Как Вам спастись? (D.Friedman) G>Update28.b Какие у орков могут быть контр-приемы?
Сегодня был на собеседовании на должность зам. директора. Заполняю анкету. Там попадается вопрос:
"Представьте себе, что вы — Эльф. За вами гонятся злые Орки. У вас с собой лук и стрелы, вы отлично стреляете из лука и способны одним выстрелом убить Орка. Проблема в том, что стрел у вас пять, а Орков за вами гонится десять. Что вы будете делать?"
Думал я, думал, потом написал, что в последний раз, когда со мной такое приключилось, в палату зашли санитары, Орков в смирительные рубашки нарядили, а у меня лук со стрелами отобрали. И, довольный собой, даю заполненную анкету девушке, которая проводит собеседование. Она всё это дело читает, делает какие-то заметки, доходит до этого вопроса, поднимает на меня взгляд и говорит:
— Вы второй человек, который таким образом отвечает на этот вопрос. Первым был директор. Он ответил "Брошу пить". Мне почему-то кажется, что вы нам подойдёте.
EX>5-)Хм... Ну в общем-то вроде бы есть два общих способа: EX>I) реактивный EX>II) взаимодействие с окружающей средой
Подпрыгивать вверх. Правда, выбрать берег к которому полетим не получиться.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[2]: Интересные задачки для программистов
От:
Аноним
Дата:
11.08.06 12:35
Оценка:
Здравствуйте, ghost92, Вы писали:
G>>13. На консоли Xbox адрес пикселя с координатами x, y записывается в двоичной форме как x7 y7 x6 y6 x5 y5 x5 y5 x4 y4 x3 y3 x2 y2 x1 y1 x0 y0 (где xn, yn — соответствующие биты чисел x и y). Дан пиксель с адресом a, найти адрес его соседа справа (Visual Concepts)
G>P — точка. G>сосед справа (( P | 1010101010101010 ) + 2) & ( P | 0101010101010101 )
Здравствуйте, Spidola, Вы писали:
S>Здравствуйте, Grammer, Вы писали: G>>15. Дано число. Определить, является ли оно целой степенью 2. (Microsoft и другие)
S>Мне всегда нравилась эта задачка, поскольку непрограммисту и в голову не придёт думать на уровне битов
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, Кодт, Вы писали:
G>>>5а. Вы сидите в лодке, плавающей посреди небольшого озера. У Вас собой на борту есть большой кирпич. Если выкинуть его в озеро, уровень воды увеличится? уменьшится? останется неизменным? (популярный вопрос, на многих фирмах задают, в том числе на и Микрософте)
К>>Не изменится. Водоизмещение пары лодка+кирпич не зависит от занимаемого ими объёма.
А>Уменьшится. Все-таки плотность кирпича больше плотности воды, поэтому будучи в лодке, он вытеснит больше воды, чем сам, пойдя ко дну. Исключения типа водоплавающих кирпичей пока не рассматриваем
Насколько помню из курса физики:
mg = Fapx
m1*g + m2*g = Fapx,
где m1 и m2 — массы кирпича и локи соответственно.
Значит уровень не изменится, поскольку общий вес вытесняемой воды не изменится.
Здравствуйте, FoolS.Top, Вы писали:
FT>Здравствуйте, Spidola, Вы писали:
S>>Здравствуйте, Grammer, Вы писали: G>>>15. Дано число. Определить, является ли оно целой степенью 2. (Microsoft и другие)
S>>Мне всегда нравилась эта задачка, поскольку непрограммисту и в голову не придёт думать на уровне битов
FT>Об этой задаче здесь уже было. Напомню решение
FT>
FT>if (!((x - 1) & x))
FT>{
FT> // x - целая степень 2
FT>}
FT>
Здравствуйте, Arioch2, Вы писали:
A>Думаю, примерно так: на входе
Интересно. Если длина буферов и строк одинакова, то тут всё просто.
Если длина строк разная, то я вижу здесь два пути: либо просто инвертировать строки и потом переслать их на начало буферов (в лоб), либо определить наибольший буфер и инвертировать строки в пределах его. В первом случае тройной проход каждого буфера. Во втором — тоже три прохода, но не до конца буферов (чем меньше заполнены, тем меньше времени на задачу).
Здравствуйте, Grammer, Вы писали:
G>30. Почему в стандарте С++ не позволено по умолчанию преобразовывать char** в const char**? Напишите пример кода, где такое преобразование (если бы его разрешили) привело бы к ошибке. (С++ faq)
Почему нельзя понимаю (char** должен преобразовываться const char * const * ).
Только вот код придумать не могу.
Здравствуйте, Smal, Вы писали:
G>>30. Почему в стандарте С++ не позволено по умолчанию преобразовывать char** в const char**? Напишите пример кода, где такое преобразование (если бы его разрешили) привело бы к ошибке. (С++ faq)
S>Почему нельзя понимаю (char** должен преобразовываться const char * const * ). S>Только вот код придумать не могу.
"Smal" <54740@users.rsdn.ru> wrote in message news:2100914@news.rsdn.ru... > Здравствуйте, Grammer, Вы писали: > > G>30. Почему в стандарте С++ не позволено по умолчанию преобразовывать char** в const char**? Напишите пример кода, где такое преобразование (если бы его разрешили) привело бы к ошибке. (С++ faq) > > Почему нельзя понимаю (char** должен преобразовываться const char * const * ). > Только вот код придумать не могу.
Вот пример, иллюстрирующий взлом константности, в случае, если разрешено преобразование char** в const char**:
char buffer[256];
char* p = buffer;
const char** cpp = &p; //Предположим, что это преобразование разрешено
*cpp = "Hello, world"; //Теперь указатель p указывает на константную строку!!!
p[0] = '!'; //Access violation
Posted via RSDN NNTP Server 2.0
--
Справедливость выше закона. А человечность выше справедливости.
"Smal" <54740@users.rsdn.ru> wrote in message news:2101246@news.rsdn.ru... > Здравствуйте, rg45, Вы писали: > > R>
> R> char buffer[256];
> R> char* p = buffer;
> R> const char** cpp = &p; //Предположим, что это преобразование разрешено
> R> *cpp = "Hello, world"; //Теперь указатель p указывает на константную строку!!!
> R> p[0] = '!'; //Access violation
> R>
> > Но ведь это ничем не отличается от >
> char buffer[256];
> char* p = buffer;
> const char* cpp = p; //Это преобразование разрешено
> cpp = "Hello, world"; //Теперь указатель p указывает на константную строку!!!
> p[0] = '!'; //Access violation
>
Отличается существенно. Во втором случае значение указателя p меняется: он всю дорогу указывает на массив buffer. Во втором же случае мы добиваемся того, что указатель p начинает указывать на строковый литерал!
Posted via RSDN NNTP Server 2.0
--
Справедливость выше закона. А человечность выше справедливости.
Здравствуйте, rg45, Вы писали:
R>Отличается существенно. Во втором случае значение указателя p меняется: он всю дорогу указывает на массив buffer. Во втором же случае мы добиваемся того, что указатель p начинает указывать на строковый литерал!
>> R> char buffer[256];
>> R> char* p = buffer;
>> R> const char** cpp = &p; //Предположим, что это преобразование разрешено
>> R> *cpp = "Hello, world"; //Теперь указатель p указывает на константную строку!!!
>> R> p[0] = '!'; //Изменяем первый символ массива литерала "Hello World!!!"
>> R>
>> >> Но ведь это ничем не отличается от >>
>> char buffer[256];
>> char* p = buffer;
>> const char* cpp = p; //Это преобразование разрешено
>> cpp = "Hello, world"; //Указатель p попрежнему направлен на buffer
>> p[0] = '!'; //Изменяем первый символ в массиве buffer
..>
> > Отличается существенно. Во втором случае значение указателя p меняется: он всю дорогу указывает на массив buffer. В первом же случае мы добиваемся того, что указатель p начинает указывать на строковый литерал!
Posted via RSDN NNTP Server 2.0
--
Справедливость выше закона. А человечность выше справедливости.
Здравствуйте, VsevolodC, Вы писали:
VC>Здравствуйте, andyJB, Вы писали:
JB>>Здравствуйте, VsevolodC, Вы писали:
VC>>>и оно выполняется, потому что ранее названных нет. JB>>И что? Второй назовет произвольное число, отличное от 1, и игра продолжится.
VC>Действительно, не сообразил. Однако можно первым назвать -1.
я думаю если там сказано "разменная монета", то это само собой подразумевает что минимальное число это 1. а не 0 и не -1.
Здравствуйте, FoolS.Top, Вы писали: G>>>15. Дано число. Определить, является ли оно целой степенью 2. (Microsoft и другие) FT>Об этой задаче здесь уже было. Напомню решение
FT>
FT>if (!((x - 1) & x))
FT>{
FT> // x - целая степень 2
FT>}
FT>
все понятно, но 0 исключение или как?
Государство должно защищать свободу и право, в этом его оправдание.
G>22. Стандартный способ "честного" деления пирога: первый участник делит, второй выбирает себе один из кусков, оставшийся кусок достается первому. Что делать если участников 3? (Мартин Гарднер, чтоли?)
1-ой делит на две части, 2-ой делит любой кусок на две части, 3 выбирает себе любой кусок от последнего деления, оставшийся забирает 2-ой.
2-ой делит на две части кусок от первого деления и т.д. после трех таких процедур у каждого будет по 2 куска.
Государство должно защищать свободу и право, в этом его оправдание.
Здравствуйте, Grammer, Вы писали: G>25. У вас есть зажигалка и веревка. Если веревку поджечь с конца, то она вся сгорит за полчаса. Как отмерить, при помощи этих двух предметов 15 минут? Важное обстоятельство: Веревка горит неравномерно, где-то быстрее, где-то медленнее. (очень популярная задача)
Поджечь с двух сторон, как только вся веревка сгорит пройдет 15 минут.
Государство должно защищать свободу и право, в этом его оправдание.
seafresh wrote:
> 1-ой делит на две части, 2-ой делит любой кусок на две части, 3 выбирает > себе любой кусок от последнего деления, оставшийся забирает 2-ой.
Так не годится, если 2-й и 3-й будут в сговоре, 1-му может ничего не остаться.
Допустим есть 100 частей. 1-ый делит на 34 и 66. 2-й делит кусок 34 на 1 и 33. 3-й забирает 66, 2-й забирает 33 , а 1-му
достаётся 1 частичка, и он ничего сделать не может.
> 2-ой делит на две части кусок от первого деления и т.д. после трех таких процедур у каждого будет по 2 куска.
Непонятно что подразумевается под "и т.д"?
Posted via RSDN NNTP Server 2.0
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
К>Возьмём некоторый начальный набор M0. s0=start(M0), g0=gcd(M0). К>Разобьём множество натуральных чисел на две части: V0 = [1..s0*g0], N0 = N\V0.
К>Предположим, что наша игра бесконечна. Это значит, что рано или поздно мы начнём делать ходы из N1. (Поскольку N0 конечно).
Что такое N1? Почему множество N0 конечно? "\" означает разность множеств или нет?
Здравствуйте, Wass, Вы писали:
W>Что такое N1? Почему множество N0 конечно?
Да, интересно... мне уже сходу не разобраться в том, что я понаписал тогда.
Видимо, переименовывал что-то в процессе да недопереименовал.
W> "\" означает разность множеств или нет?
Да, разность.
Попробую восстановить ход мысли и переписать заново. Чуть позже.
Здравствуйте, kan, Вы писали:
kan>seafresh wrote: >> 2-ой делит на две части кусок от первого деления и т.д. после трех таких процедур у каждого будет по 2 куска. kan>Непонятно что подразумевается под "и т.д"?
Первый делит целый торот на две части, второй выбирает любую часть и делит ее на две части, третий выбирает любую часть из двух от второго, остаток для второго.
Второй делит часть на две части, третий выбирает любую часть и делит ее на две части, первый выбирает любую часть из двух от третьего, остаток для третьего.
Первый делит часть на две части, второй выбирает любую часть из двух от первого, остаток для первого.
Таким образом у каждого будет по два куска, но тут есть один недостаток для первого едока.
А вот кстати второй дискретный вариант, первый делит торт на три куска, затем второй берет себе любой кусок, третий берет себе любой из оставшихся двух,
а последний достается первому.
Т.е. нет никакой поножовщины, из-за того, что кому-то скорость ножа показалась слишком быстрой, или что кто-то охрип в неподходящий момент, или что кто-то пропел с хором с кем-то.
Государство должно защищать свободу и право, в этом его оправдание.
Здравствуйте, VsevolodC, Вы писали:
VC>Здравствуйте, Grammer, Вы писали:
G>>2a. Два игрока играют по очереди называют число, достоинство воображаемой разменной монеты. При этом нужно, чтобы это число нельзя было выплатить при помощи ранее называнных монет. Проигрывает назвавший число 1. Доказать, что игра не может продолжаться бесконечно. (J.H.Conway)
VC>Очевидно, выигрывает первый игрок, назвав 0
есть множество монет М из натуральных чисел [2..inf]
возьмем произвольное n из M.
произведения С*n (где С — натуральная константа) покроет с шагом n все значения от n
n n
+-----------------+------------------+
| | |
....n................2n.................3n..........
надо доказать, что все числа из диапозона [n..2n] прокроют все числа из диапозона [2n..3n] и всех последующих
.
2n + k = n + n + k
где k < n
т.е. вариантов даже не n, а намного меньше
вывод: перебрав варианты из [n..2n] придется перейти к [2..n]
те вариантов не больше чем 2n.
даже если не закрывать всех чисел в текущем диапозоне, а переходить к следующему, то с каждым названным числом мы будем закрывать числа во всех диапозонах впереди текущего — рано или поздно закроем все и придется двигаться назад.
Здравствуйте, VsevolodC, Вы писали:
VC>Здравствуйте, Grammer, Вы писали:
G>>32. Как передвинуть гору Фудзи? (Microsoft)
VC>1. Метод теории относительности: передвинуть наблюдателя
VC>2. Метод малых приращений: положить камень на вершину горы + епсилон
VC>3. Топонимический метод: поменять названия Фудзи с другой горой
VC>4. Координатный метод: поменять систему координат
VC>5. Метрический метод: померить координаты горы 2 раза, значения в 99.9% случаев будут разные
VC>6. Геологический метод: дождаться очередных геологических изменений в регионе
VC>фантазия закончилась
миллион китайцев за чашку риса сдвинут ее куда угодно причем до оконцания текущей пятилетки
7. У вас есть 8 с виду одинаковых монет, одна из которых, тем не менее, фальшивая. Фальшивая монета чуть тяжелее, но во всем остальном идентична настоящим. У вас также есть, в лучших традициях жанра, весы с чашечками, как у богини правосудия. За какое минимальное число взвешиваний можно определить фальшивку? (популярная задача)
Решается за 2 взвешивания.
Делим 8 монет на 3 кучки. 3 + 3 + 2.
Взвешиваем 3 и 3. Варианты:
— Если кучки равны, значит их убираем и взвешиваем оставшиеся 2 монеты.
— Если какая-то кучка перевешивает, то из этой кучки берём 2 монеты и взвешиваем. Если они равны, то та монета, которая осталась — фальшивая. Если какая-то монета перевешивает, то она и есть фальшивая.
Здравствуйте, seafresh, Вы писали:
S>Здравствуйте, kan, Вы писали:
S>А вот кстати второй дискретный вариант, первый делит торт на три куска, затем второй берет себе любой кусок, третий берет себе любой из оставшихся двух, S>а последний достается первому. S>Т.е. нет никакой поножовщины, из-за того, что кому-то скорость ножа показалась слишком быстрой, или что кто-то охрип в неподходящий момент, или что кто-то пропел с хором с кем-то.
немного надо дополнить:
2й и 3й должны сложить свои куски и поделить по новой на двоих
seafresh wrote:
> Первый делит целый торот на две части, второй выбирает любую часть и > делит ее на две части, третий выбирает любую часть из двух от второго, > остаток для второго. > Второй делит часть на две части, третий выбирает любую часть и делит ее > на две части, первый выбирает любую часть из двух от третьего, остаток > для третьего. > Первый делит часть на две части, второй выбирает любую часть из двух от > первого, остаток для первого. > Таким образом у каждого будет по два куска, но тут есть один недостаток > для первого едока.
Что-то слишком сложно. Но деление на две части/объединение 2-х частей каждый раз, по-моему никак не даст 1/3 через
конечное число шагов.
> А вот кстати второй дискретный вариант, первый делит торт на три куска, > затем второй берет себе любой кусок, третий берет себе любой из > оставшихся двух, а последний достается первому.
Первый и второй в сговоре. Первый делит 100 на 98/1/1 — второй забирает 98, третьему достаётся только 1.
Третьим будешь?
> Т.е. нет никакой поножовщины, из-за того, что кому-то скорость ножа > показалась слишком быстрой, или что кто-то охрип в неподходящий момент, > или что кто-то пропел с хором с кем-то.
Неа, не работает.
Posted via RSDN NNTP Server 2.0
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Максим Алексейкин wrote:
> S>А вот кстати второй дискретный вариант, первый делит торт на три > куска, затем второй берет себе любой кусок, третий берет себе любой из > оставшихся двух, > S>а последний достается первому. > немного надо дополнить: > 2й и 3й должны сложить свои куски и поделить по новой на двоих
Так вроде работает.
Хотя я слышал другой вариант решения, легко обобщаемый на любое кол-во. Вначале двое делят между собой, потом каждый из
них делит свою долю на 3 части. Третий выбирает у каждого по одному кусочку.
И вместо торта делили мешок золотого песка, который позволяет делить/объединять доли легче чем торт.
Posted via RSDN NNTP Server 2.0
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Здравствуйте, ghost92, Вы писали:
G>Здравствуйте, Grammer, Вы писали:
G>>7. У вас есть 8 с виду одинаковых монет, одна из которых, тем не менее, фальшивая. Фальшивая монета чуть тяжелее, но во всем остальном идентична настоящим. У вас также есть, в лучших традициях жанра, весы с чашечками, как у богини правосудия. За какое минимальное число взвешиваний можно определить фальшивку? (популярная задача) G>2 достаточно. можно и с 9ю монетами справиться.
Здравствуйте, Grammer, Вы писали:
G>2a. Два игрока играют по очереди называют число, достоинство воображаемой разменной монеты. При этом нужно, чтобы это число нельзя было выплатить при помощи ранее называнных монет. Проигрывает назвавший число 1. Доказать, что игра не может продолжаться бесконечно. (J.H.Conway)
А кто-нибудь решил эту задачу? Я решение придумал, но может быть можно проще.
ИМХО, это решение неверно. Непонятно, почему нам удасться закрыть хотябы один
диапазон вида [kn, (k+1)n].
даже если не закрывать всех чисел в текущем диапозоне, а переходить к следующему, то с каждым названным числом мы будем закрывать числа во всех диапозонах впереди текущего — рано или поздно закроем все и придется двигаться назад.
Всегда есть некоторое простое число, которое больше всех названных чисел. Оно не покрыто не одним числом.
А почему его можно покрыть линейной комбинацией этих чисел, совершенно непонятно.
S>ИМХО, это решение неверно. Непонятно, почему нам удасться закрыть хотябы один S>диапазон вида [kn, (k+1)n].
S>
S>даже если не закрывать всех чисел в текущем диапозоне, а переходить к следующему, то с каждым названным числом мы будем закрывать числа во всех диапозонах впереди текущего — рано или поздно закроем все и придется двигаться назад.
S>Всегда есть некоторое простое число, которое больше всех названных чисел. Оно не покрыто не одним числом. S>А почему его можно покрыть линейной комбинацией этих чисел, совершенно непонятно.
меня не интересуют простые числа, я не раскладываю их на множители
любое хоть простое хоть не простое число войдет в один их диапозонов [kn, (k-1)n) и будет закрыто при переборе максимум n чисел из диапозона [n, number-1].
мы можем использовать числа несколько раз, т.е.
для [n, 2n) и [2n, 3n)
2n = n + n
2n + 1 = n + (n + 1)
2n + 2 = n + (n + 2)
...
2n + (n — 1) = n + (n + (n — 1))
ну и общий случай [kn, (k-1)n)
kn = n + n + .... n k times
kn + 1 = n + n + .... + n + 1
Первый делит пирог на 3 части.
Два других юзера делают заявки на полученные куски.
Если заявки разные, каждый берет свой кусок — задача решена.
Если заявки совпали:
--Эти два юзера делят "конфликтный" кусок между собой.
--Делают заявки на двух оставшихся кусках.
----Если заявки совпали, делят "конфликтный" кусок между собой — задача решена.
----Если заявки разные, делят каждый свой заявленный кусок с первым юзером.
Алгоритм деления с заявками можно положить на любое (n) количество юзеров:
Первый юзер делит на n частей.
Далее каждый "конфликтный кусок" делятся на n-1 частей между m юзерами. m (1<m<n) — это количество претендентов на кусок. Каждый из этих m юзеров получает разную долю (или одинаковую, если m=n-1). Остальные куски ("конфликтные" и не только) делятся, с учетом: кто сколько долей уже имеет.
Итд.
Здравствуйте, Максим Алексейкин, Вы писали:
МА>может коряво объясняю, смысл: если закрыли (n+c), то закрыли все (kn + c) где k from [2, бесконечность], а c константа
Да. Только почему будут названы хотя бы два числа стоящих рядом?
Пример: всегда называть числа делящиеся на 4.
(Я понимаю, что в этом случае задача сводится к исходной.)
А если каждое следующее число будет, скажем, (n! + 1), где n > 3. Или что-то в этом роде..?
Здравствуйте, Smal, Вы писали:
S>Здравствуйте, Максим Алексейкин, Вы писали:
МА>>может коряво объясняю, смысл: если закрыли (n+c), то закрыли все (kn + c) где k from [2, бесконечность], а c константа S>Да. Только почему будут названы хотя бы два числа стоящих рядом? S>Пример: всегда называть числа делящиеся на 4. S>(Я понимаю, что в этом случае задача сводится к исходной.)
S>А если каждое следующее число будет, скажем, (n! + 1), где n > 3. Или что-то в этом роде..?
да наздоровье, главное, что больше n чисел не назовеш, двигаясь только вперед конечно.
как только назовешь n-ное по счету (уникальное и не выводимое из предыдуших) вперед двигаться будет некуда.
(на самом деле меньше чем n)
(n! + 1) = kn + c — это всегда выполнится при некоторых k и c, где c < n.
Хм. Я еще раз перечитал первое сообщение и понял, что изначально неправильно понял про заполнение интервалов.
Теперь все стало ясно. Мои извинения, что так долго тормозил.
Здравствуйте, Максим Алексейкин, Вы писали:
МА> МА>ваше решение в студию
Я основывался на аналогии с Диофантовыми уравнениями.
Пусть среди названых чисел будут два взаимно простых числа a и b.
(В случае, если все числа имеют некоторый общий делитель, задача сводится к исходной).
Так как НОД(a,b) = 1, то существуют M и N, такие что aM + bN = 1.
Одно из чисел M и N будет отрицательно. Пусть это будет M.
Тогда любое число из промежутка [-a^2M, -a^2M + a] представляется в виде
-a^2M + (aM + bN) * k = aM(k - a) + bN, k <= a.
Ну, а для следующих промежутков просто прибавляется a.
G>>5b. Кусок замороженного спирта в бочке с пивом. Что станет с уровнем жидкости, когда спирт весь растает? (не понмню откуда)
К>Объём тающего спирта увеличивается, а объём охлаждаемой воды — уменьшается (до 4°С), затем снова увеличивается. К>Объём водно-спиртовой смеси — меньше объёмов каждого из компонентов. К>При растворении спирта выделяется тепло. К>Бочка может быть термостабилизированной или термоизолированной. Колебания объёма могут быть изобарическими или сопровождаться колебаниями давления. При этом может затрачиваться разное количество энергии (одно дело пробулькать водяной затвор, другое — деформировать бочку, третье — сатурация или десатурация пива углекислым газом).
К>В общем, идёт довольно затейливый процесс, суммарный эффект варьируется и от количества веществ, и от начальной температуры, и от других условий.
Плавающий спирт порядочно торчит над пивом, а когда растает растечется равномерным слоем, т.е. уровень повыситься
Здравствуйте, rm822, Вы писали:
R>Плавающий спирт порядочно торчит над пивом, а когда растает растечется равномерным слоем, т.е. уровень повыситься
Пиво охладится за счёт таяния спирта и сожмётся, т.е. уровень понизится.
Объём спирто-водяного раствора меньше, чем сумма объёмов жидкого спирта и воды (при той же температуре), т.е. уровень опять понизится.
При растворении жидкого спирта в воде выделяется тепло, пиво нагреется, т.е. уровень повысится.
Растворимость углекислого газа в спирто-водяных растворах разной концентрации и разной температуры тоже разная — если произойдёт десатурация, то снова объём понизится.
Скомпенсируют ли эти колебания исходное повышение уровня — это вопрос.
Здравствуйте, ArtemGorikov, Вы писали:
AG>Здравствуйте, ghost92, Вы писали:
G>>Здравствуйте, Grammer, Вы писали:
G>>>7. У вас есть 8 с виду одинаковых монет, одна из которых, тем не менее, фальшивая. Фальшивая монета чуть тяжелее, но во всем остальном идентична настоящим. У вас также есть, в лучших традициях жанра, весы с чашечками, как у богини правосудия. За какое минимальное число взвешиваний можно определить фальшивку? (популярная задача) G>>2 достаточно. можно и с 9ю монетами справиться.
AG>2 недостаточно. 8->4->2. Итого 3 сравнения.
Более чем
1е взвешивание 3,3,2
2е взвешивание 1,1,1 или 1,1
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[2]: Интересные задачки для программистов
От:
Аноним
Дата:
16.11.06 07:43
Оценка:
Здравствуйте, seafresh, Вы писали:
S>Здравствуйте, Grammer, Вы писали: G>>25. У вас есть зажигалка и веревка. Если веревку поджечь с конца, то она вся сгорит за полчаса. Как отмерить, при помощи этих двух предметов 15 минут? Важное обстоятельство: Веревка горит неравномерно, где-то быстрее, где-то медленнее. (очень популярная задача)
S>Поджечь с двух сторон, как только вся веревка сгорит пройдет 15 минут.
но веревка ведь горит не равномерно? разве ваше решение верно?
Здравствуйте, Аноним, Вы писали:
S>>Поджечь с двух сторон, как только вся веревка сгорит пройдет 15 минут.
А>но веревка ведь горит не равномерно? разве ваше решение верно?
конечно верно, ведь суммарно вся она сгорит в 2 раза быстрее
30
15 15
+----------+------------------+
это часть длиннее, но горит быстрее
Здравствуйте, Arioch, Вы писали:
A>On Wed, 01 Feb 2006 19:46:41 +0300, vitaly_spb <19231@users.rsdn.ru> wrote:
>> А>Уменьшится. Все-таки плотность кирпича больше плотности воды, поэтому >> будучи в лодке, он вытеснит больше воды, чем сам, пойдя ко дну. >> >> А почему так можно поподробнее?
A>A куда подробнее ?
A>Плавающий предмет вытесняет воду равную своему весу. Утонувший — равную A>своему объему.
как понять эту фразу? сколько в итоге воды вытеснится массой?
A>Сравни сколько воды вытеснит плавающий и утонвший кирпич. Чем больше воды A>вытеснено — тем выше уровень A>-- A>Отправлено M2, революционной почтовой программой Opera: A>http://www.opera.com/mail/
Здравствуйте, Grammer, Вы писали:
G>1. Даны 2 буфера фиксированной длины. В начале каждого лежат данные (строчки текст), дальне до конца нули. Поменять строчки местами и перевернуть их задом на перед, так, чтобы в итоге нули опять находились в конце, а текст — в начале. (Microsoft)
Здравствуйте, seafresh, Вы писали:
G>>22. Стандартный способ "честного" деления пирога: первый участник делит, второй выбирает себе один из кусков, оставшийся кусок достается первому. Что делать если участников 3? (Мартин Гарднер, чтоли?)
S>1-ой делит на две части, 2-ой делит любой кусок на две части, 3 выбирает себе любой кусок от последнего деления, оставшийся забирает 2-ой. S>2-ой делит на две части кусок от первого деления и т.д. после трех таких процедур у каждого будет по 2 куска.
все это глупости. пихаем торт в мясорубку, и каждому выдаем по половине (трети, четверти, и т.д.) от того что получилось
I'm the hero I'm back
With weapons and with magic spells
Здравствуйте, Crab, Вы писали:
C>все это глупости. пихаем торт в мясорубку, и каждому выдаем по половине (трети, четверти, и т.д.) от того что получилось
Тот, кто облизывает мясорубку, получит преимущество.
Ну да, я бы сказал, что после первого хода любые N-1 ходов закроют всё на "бесконечности", то есть с числа, максимального из всех ранее названных и придётся двигаться назад.
15. Дано число. Определить, является ли оно целой степенью 2. (Microsoft и другие)
// is the value power of two?int _tmain(int argc, _TCHAR* argv[])
{
unsigned long int value = 0, rest, startValue;
std::cout<<"Is the value power of two? Input value : "<<std::endl;
do
{
std::cin>>value;
startValue = value;
rest = 0;
if(startValue == 2 || startValue == 1)
{
value = 0;
}
if(startValue == 0 )
{
value = 0;
rest = 1;
}
while(value)
{
rest = value % 2;
value /= 2;
if (value == 2 || rest ==1 )
{
break;
}
}
if (rest == 0)
std::cout<<"The value "<<startValue << " is a power of two"<<std::endl;
else
std::cout<<"The value "<<startValue << " is Not a power of two"<<std::endl;
}while(true);
return 0;
}
Здравствуйте, Багер, Вы писали:
Б>Насчёт задачки про два выключателя на одну лампочку. Б>Решение, использующееся у меня на даче — один обыкновенный переключатель, один двойной. Б>Есть другие решения?
Избавиться нафиг от проводов и заменить выключатели на мышей, прибитых к стенке. При клике по любой кнопки мыши программа посылает соответствующий пакет по WiFi — его ловит комп управляющий лампой и меняет состояние лампы не противоположное.
Здравствуйте, phys, Вы писали:
P>Здравствуйте, phys, Вы писали:
P>15. Дано число. Определить, является ли оно целой степенью 2. (Microsoft и другие)
много кода поскипано.....
ЖЕСТЬ!!!!
а может проще так:
bool isPowerOfTwo( int v ){ return (!(v & (v - 1)) && v); }
ЗЫ: анек в тему
задача определить является ли число V четным.
ответ:
1.программер форм на VB — (SELECT PARITY FROM ALLINTERGERS WHERE VALUE=V)
2.начинающий программер(индус) V%2==0
3.нормальный программер — !(V&1)
_JoKe_ wrote:
> bool isPowerOfTwo( int v ){ return (!(v & (v — 1)) && v); }
> ЗЫ: анек в тему > задача определить является ли число V четным. > ответ: > 1.программер форм на VB — (SELECT PARITY FROM ALLINTERGERS WHERE VALUE=V) > 2.начинающий программер(индус) V%2==0 > 3.нормальный программер — !(V&1)
А я придумал перебором:
индус без обид — оцени твоей функции надо столько итераций сколько бит в числе, при этом есть условные переходы, которые могут конвеер сбросить
к тому же ошибка в цикле надо писать не i << 1 а i<<=1
моей меньше 10 тактов которые никогда не вызывают перегруз процессорного конвеера
Здравствуйте, _JoKe_, Вы писали:
_JK>Здравствуйте, phys, Вы писали:
P>>Здравствуйте, phys, Вы писали:
P>>15. Дано число. Определить, является ли оно целой степенью 2. (Microsoft и другие) _JK>много кода поскипано..... _JK>ЖЕСТЬ!!!!
_JK>а может проще так: _JK>
_JK>bool isPowerOfTwo( int v ){ return (!(v & (v - 1)) && v); }
_JK>
Здравствуйте, Аноним, Вы писали:
А>_JoKe_ wrote:
>> bool isPowerOfTwo( int v ){ return (!(v & (v — 1)) && v); }
>> ЗЫ: анек в тему >> задача определить является ли число V четным. >> ответ: >> 1.программер форм на VB — (SELECT PARITY FROM ALLINTERGERS WHERE VALUE=V) >> 2.начинающий программер(индус) V%2==0 >> 3.нормальный программер — !(V&1) А>А я придумал перебором: А>
Здравствуйте, phys, Вы писали:
P>Здравствуйте, _JoKe_, Вы писали:
_JK>>Здравствуйте, phys, Вы писали:
P>>>Здравствуйте, phys, Вы писали:
P>>>15. Дано число. Определить, является ли оно целой степенью 2. (Microsoft и другие) _JK>>много кода поскипано..... _JK>>ЖЕСТЬ!!!!
_JK>>а может проще так: _JK>>
_JK>>bool isPowerOfTwo( int v ){ return (!(v & (v - 1)) && v); }
_JK>>
P>это не работает ....
я ошибся — работает видимо я на уровне начинающего индуса , но я почему то по этому поводу не переживаю
phys wrote: > P>>>15. Дано число. Определить, является ли оно целой степенью 2. > (Microsoft и другие) > _JK>>много кода поскипано..... > _JK>>ЖЕСТЬ!!!! > > > _JK>>а может проще так: > _JK>> > > _JK>>bool isPowerOfTwo( int v ){ return (!(v & (v — 1)) && v); } > _JK>> > > > > P>это не работает .... > > я ошибся — работает видимо я на уровне начинающего индуса , но я почему > то по этому поводу не переживаю
А я думал, Вам законно не понравилась сигнатура — при такой сигнатуре и
таком условии задачи то, что код может не работать на -MAX_INT-1, не
очень приятно.
>2a. Два игрока играют по очереди называют число, достоинство воображаемой разменной монеты. При этом нужно, чтобы это число нельзя было выплатить при помощи ранее называнных монет. Проигрывает назвавший число 1. Доказать, что игра не может продолжаться бесконечно. (J.H.Conway)
Пришло не совсем честное решение. Если речь идёт также и о размене с негативным количеством монет (я тебе, ты мне), то вроде так:
a1*x1 + ... aN*xN = xN+1
Чтобы диофпнтово не решалось, каждая новая монета должна НЕ делиться на наибольшитй общий делитель всех остальных. Таким образом с каждой новой монетой НОД падает. Значит кол-во шагов конечно.
В жизни кaждoгo челoвекa бывaют приятные мoменты, кoгдa oн чувствует себя пoлным идиoтoм. Приятнoсть этих мoментoв в пoстижении истины.
Здравствуйте, Grammer, Вы писали:
G>2b. Если у нас уже есть монеты достоинствами x[0]...x[n] (каждого типа — неограниченнок количество), то можно задать вопрос: как нам выплатить данную сумму денег S минимальным общим числом монет? Напишите соответвующую программу.
/*******************************
* Если у нас уже есть монеты достоинствами x[0]...x[n]
* (каждого типа — неограниченнок количество)
* Как выплатить данную сумму денег S минимальным общим числом монет?
*/#include"stdafx.h"#include <algorithm>
#include <functional>
#include <numeric>
#include <vector>
#include <ctype.h>
using namespace std;
int values[] = {5,50,500, 10000};
vector<int> face_value;
vector<int> sequence;
typedef vector<int>::iterator Iter;
typedef vector<int>::reverse_iterator RIter;
void printVec(vector<int> &v)
{
copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
cout<<endl;
}
//count summ in secuenceint accumulateSeq()
{
return accumulate(sequence.begin(),sequence.end(), 0);
}
//punch in the value in sequencebool completeSummWithValue(int summ, int value)
{
bool result = false;
if (value > summ)
return result;
//push face values to sequence till
//the summ will be equal or GREATER then summwhile(accumulateSeq() < summ)
{
sequence.push_back(value);
}
//is there a solution ?if(accumulateSeq() == summ)
{
result = true;
}
else
sequence.pop_back(); //extract last excess valuereturn result;
}
bool deleteValueFromSeq(int value)
{
//return false if no value was foundif (find(sequence.begin(), sequence.end(), value) == sequence.end())
return false;
//remove value from the end of sequence
//because we seek max value
sequence.erase(find(sequence.rbegin(), sequence.rend(), value).base() - 1);
// printVec(sequence);return true;
}
bool first_check(int summ)
{
bool result = false;
//try to divide at max face_value first ... for (Iter iter = face_value.begin(); iter != face_value.end(); ++iter)
{
result = completeSummWithValue(summ, *iter);
if (result)
break;
}
return result;
}
bool second_check(int summ)
{
bool result = false;
RIter iter = face_value.rbegin();
iter++;
for (; iter != face_value.rend(); ++iter)
{
while(deleteValueFromSeq(*(iter)))
{
result = completeSummWithValue(summ, *(iter-1));
if (result)
break;
}
if (result)
break;
}
return result;
}
int _tmain(int argc, _TCHAR* argv[])
{
int summ;
bool result;
face_value.assign(values, values+(sizeof(values)/sizeof(values[0])));
sort(face_value.begin(), face_value.end(), greater<int>());
cout<<"Possible face_values : ";
printVec(face_value);
while(true)
{
cout<<" Input summ : "<<endl;
cin>>summ;
sequence.clear();
sequence.reserve(summ/face_value[face_value.size()-1]);
//fill the secuence from max to min values
result = first_check(summ);
if (!result)
//process the secuence from min to max
result = second_check(summ);
if (result)
{
printVec(sequence);
}
else
cout<<"Couldn't find a solution ..."<<endl;
}
return 0;
}
Здравствуйте, MaximVK, Вы писали:
MVK>Здравствуйте, olen33, Вы писали:
O>>Я больше склоняюсь к приводившемуся здесь варианту про линию, первый заступивший за которую получает стрелу в лоб, т.к. в условии сказано, что орки эгоистичные твари.
MVK>Не прокатит. Как эгоистичные твари они вытолкнут по очереди пятерых своих товарищей за черту, а потом пойдут кушать эльфа.
надо прочертить линию, стрелять в первого кто ее переступить и сразу вытаскивать стрелу...
G>>28.a (Для мэнеджеров, наверное) Вы — добрый эльф, меткий стрелок из лука. За Вами гонится отряд из 10 орков, злах и эгоистичных тварей. К счастью, они пока далеко позади. К несчастью, через какое-то время они Вас догонят и съедят. К счастью у Вас есть стрелы, которыми Вы можете разить орков наповал. К еще большему счастью, на одного орка хватает одной стрелы и бьете Вы без промаха. К несчастью, у Вас имеется только 5 стрел. К еще большему несчастью, орки об этом знают. Как Вам спастись? (D.Friedman)
Единственный нормальный ответ который я слышал — "брошу пить".
Стопудово выпил! Значит ответ — уровень уменьшится.
Перекуём баги на фичи!
