Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Delphi программирование > Паскаль, Turbo Pascal, PascalABC.NET
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 28.09.2012, 19:42   #21
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

Имеем группы A, B, C элементов разных цветов.
Ka, Kb, Kc - количество элементов в группах.
Пусть Ka-Kb=2n (n>=0). Такие две группы есть при любых раскладах.
Каждый элемент группы B спариваем с элементом нруппы A. Получаем Kb цвета C
Осталось 2n цвета A. Один элемент из каждой оставшейся пары спариваем с элементом группы C. Получаем элемент цвета B, который в свою очередь спариваем с оставшимся элементом пары - получаем элемент цвета C. Все

ADD - вот написал, только заметил прокол в логике. Это не пойдет
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию

Последний раз редактировалось Аватар; 28.09.2012 в 19:49.
Аватар вне форума Ответить с цитированием
Старый 28.09.2012, 20:24   #22
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

1) Получается что k = у всех групп. А это не так.
2) Хорошо спариваем (хотя они только встречались ) ka + k(+2)b = k*2c + 2b
опять же косяк.

Вот нашел в интернетике решение через системы уравнений :
Ответ - НЕТ

Выразим цвета при помощи переменных:
x - красный
y - зеленый
z - синий
Цвета не одинаковые а значит:
х≠у≠z
Допустим возможность образования одного цвета:
13x+15y+17z=45x или
13x+15y+17z=45y или
13x+15y+17z=45z
С условия мы знаем:
x+y=2z
x+z=2y
y+z=2x
Создадим систему:

{13x+15y+17z=45y
{x+y=2z
{x+z=2y
{y+x=2x

Решаем систему:

13x+15y+17z+x+y+x+z+y+z=45y+2x+2y+2 z

15x+17y+19z=2x+47y+2z

Выразим z через x и y:

z=(x+y)\2

15x+17y+19*((x+y)\2)=2x+47y+2*((x+y )\2)

24,5x+26,5y=3x+48y

21,5x=21,5y

x=y - а это невозможно:

красный≠зеленый


Ладно, более-менее разобрались,(еще б TinMan прокомментировал вообще бы супер было)
Вот другая (Кстати я её тоже решил)

Заключенные и переключатель
В тюрьме сидят 10 заключенных, каждый — в одиночной камере. Общаться между собой они не могут. В один прекрасный день начальник тюрьмы объявил им, что предоставляет всем шанс выйти на свободу, и предложил следующие условия: «В подвале тюрьмы есть комната с переключателем, имеющим два состояния: ON/OFF (верх/низ). Вас будут в произвольном порядке по одному приводить в эту комнату и через несколько минут уводить. Находясь в комнате, каждый из вас может либо изменить положение переключателя, либо ничего с ним не делать. Персонал тюрьмы трогать этот переключатель не будет. В какой-то момент один из вас (любой) должен сказать, что в комнате побывали все заключенные. Если он окажется прав — всех отпустят, если ошибется — вы навсегда останетесь в тюрьме. Я обещаю, что в комнате побывают все заключенные и что каждого из вас будут приводить туда снова и снова неограниченное число раз». После этого заключенным разрешили собраться и обсудить стратегию, потом развели по камерам. Что им нужно делать, чтобы гарантированно выйти на свободу?

Последний раз редактировалось Poma][a; 28.09.2012 в 21:15.
Poma][a вне форума Ответить с цитированием
Старый 29.09.2012, 01:56   #23
TinMan
Форумчанин
 
Аватар для TinMan
 
Регистрация: 05.09.2011
Сообщений: 869
По умолчанию

Мне кажется, условие (я про хамелеонов) совешенно ясное. Но все же его можно сделать еще яснее - вот так:
"На острове живут хамелеоны, принимающие 3 цвета. В некоторый момент было такое распределение: 13, 15 и 17. При встрече двух разных цветов, оба перекрашиваются в третий. Если других случаев перекрашивания не наблюдается, то может ли случиться, что все они окажутся одного цвета?"

Цитата:
Сообщение от Poma][a Посмотреть сообщение
можно пояснения на сщет a,b,c,x,y,z?
можно, ессно!

Но сначала я хотел про твое решение пару слов - Okay? Сначала хочу уточнить: инвариантом тут являются не сами остатки от деления на 3 (сами они изменяются). Их сумма (снова по модулю 3) - да, есть инвариант, но это бесполезно. Инвариантом является сам ВИД распределения этих остатков - то, что там обязательно один 0, одна 1, и одна 2 - вот это неизменно. И интересно еще - почему это так. Начав решать, некоторое время я думал про четность, но оно как-то не помогало.. И типа ради хохмы проскочила мысля - мож, "третичность" (типа как четность, но по отношению к 3)? И тут разу заметил, что вычитание 1 и прибавление 2 эквивалентны по модулю 3. И стал копать дальше.. ))

Теперь пояснения к "общему дубовому" решению..

a - начальное кол-во хамелеонов 1го цвета
b - начальное кол-во хамелеонов 2го цвета
c - начальное кол-во хамелеонов 3го цвета

пусть на некоторый момент произошло:
x - количество встреч ха. 2го и 3го цветов (с перекрашиванием в 1й)
y - количество встреч ха. 1го и 3го цветов (с перекрашиванием во 2й)
z - количество встреч ха. 1го и 2го цветов (с перекрашиванием в 3й)

если мы хотим занулить 1й и 2й цвета, то кол-во ха. 3го цвета будет a+b+c

a +2x -y -z = 0
b -x +2y -z = 0
c -x -y +2z = a+b+c

Это система, я выписываю ее матрицу (после простых преобразований) и столбец свободных членов
Код:
-2  1  1    a
 1 -2  1    b
 1  1 -2   -(a+b)
Детерминант матрицы равен 0 (поскольку сумма двух строк дает минус третью). Следовательно, система либо не имеет решений, либо имеет бесконечно много, и конкретный результат зависит от столбца свободных членов, то есть от конкретных значений a, b, c. Разберем пару случаев..

1. a=b=c=1,
столбец свободных членов:
1
1
-2
Подставляем его на место первого столбца матрицы. Получившаяся матрица снова имеет нулевой детерминант. Следовательно, решений бесконечное число. Это согласуется с тем, что этот случай имел бы ответ ДА (встречаются два любых, и все становятся одного цвета).

2. Наш случай. Лень выписывать (муторно переключать раскладку)).
Подстановка свободного на место любого дает матрицу с ненулевым детерминантом. Следовательно, решений нет.

addendum
Строго говоря, это решение нужно провести для всех пар цветов, для какой-то одной пары может найтись решение. Но в нашем случае решений нет ни для какой пары.
Предпочитаю на "ты".

Последний раз редактировалось TinMan; 29.09.2012 в 11:46.
TinMan вне форума Ответить с цитированием
Старый 30.09.2012, 21:03   #24
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

Огромное спасибо!
Да-да. Согласен. Всё верно.
Спасибо за разъяснения.
Poma][a вне форума Ответить с цитированием
Старый 30.09.2012, 23:24   #25
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

1. Заключенные выбирают ведущего
2. Только он может включить и включает, как только видит выключенный
3. Остальные - только выключать и каждый не более 2 раз и выключают, как только видят включенный (если лимит не исчерпан)
4. Как только ведущий насчитает 17 своих включений можно смело идти на свободу

Одного выключения для каждого из остальных не достаточно - ведущий не знает начального положения выключателя

add

В случае, если первый раз ведущий находит выключатель в положении выключено 17 раз маловато, а 18 в самый раз
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию

Последний раз редактировалось Аватар; 01.10.2012 в 07:32.
Аватар вне форума Ответить с цитированием
Старый 01.10.2012, 21:45   #26
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

Ага-ага. Сам долго просидел когда модератор задал вопрос про преодоление неизвестности начального положения выключателя.

Ок.
Еще одна. Пусть хоть кто-то развлечется
И так есть кольцевая дорога, на ней стоит n заправок (стоя эти заправки Random'но). Есть старый Вазик, с огромным баком, который вмещает любое кол-во бензина (Умели же люди машины делать ). Так же известно, что суммарного кол-ва бензина нам хватит что бы доехать из нашей точки в конечную точку (=наша начальная точка). Нужно доказать что есть такая точка, от которой можно начать движение и гарантированно мы попадем в место начала движения.

Я решал так (поскольку моё решение может "вытолкнуть" Вашу гениальную мысль, то я выделил беленьким, кому надо тот выделит, другой же пройдет мимо) :
от противного доказал что-то, и рекурсия
Poma][a вне форума Ответить с цитированием
Старый 02.10.2012, 04:14   #27
TinMan
Форумчанин
 
Аватар для TinMan
 
Регистрация: 05.09.2011
Сообщений: 869
По умолчанию

Эх, жалко, что тут нет тега [spoiler] или [hide], чтоб скрывать свой ответ от тех, кто хочет еще подумать. Можно, конечно, делать как Ромаха (красить ответ в белый цвет), но это не очень здорово смотрится. Я за все выходные (!) так и не смог выбрать времени подумать как следует над задачей про заключенных и выключатель.. А задача хорошая, и теперь уже мозги не почистишь, память не сотрешь, свой hard drive в башке не переформатируешь.. )) В любом случае - спасибо и за задачу, и за решение!

Теперь по поводу следующей задачи - "ралли консервной банки по Галактике" )). Лирическое отступление: сделать машину с большим баком совсем несложно: надо просто весь салон отвести под бензобак. Даже удивительно, что ВАЗовские конструкторы не додумались до такого. Водителю не хватит места? фигня, пусть выходит и тянет машинку за собой на вервочке.. Кстати, вы этом случае и подкапотное пространство тоже можно освободить от уже ненужного двигателя и использовать под бензобак! А как же люди, спросите вы? А пусть goto на поле, пахать.. )) Самое интересное, что, в отсутствие двигателя, расход бензина падает практически до нуля - и получаем экологически чистый автомобиль, способный проехать неограниченное расстояние на одной заправке.. Задача, мне кажется, несложная (проще предыдущих), но в ней все же есть своя изюминка. Нижеследующее адресуется Ромахе, начавшему разговор белым по белому..
<< hidden text begins <<
Что ты имеешь в виду под "рекурсией"? Извини, но мы говорим не про программу на Pascal/C/etc! Может, ты подразумевал индукцию? Если да, то - я сомневаюсь, что она тут применима..
>> end of hidden text >>
Предпочитаю на "ты".
TinMan вне форума Ответить с цитированием
Старый 02.10.2012, 19:54   #28
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

Продолжим белые дебаты :
Именно рекурсия(может в математике называется по-другому (кажется не официальное название - Метод Чайника(тоесть
- Как заварить чай?
- Берем чайник наливаем воду, .....
- А если в чайнике уже вода?
- Ставим на плиту,...
- А математик сказал бы так : выливаем воду, получаем предыдущюю задачу, которая уже решена
))) Здесь же (Шаг А1) я доказал что-то (от противного), (Шаг А2) и на основании этого доказательства, рассматривал движение от одной(произвольной) точки, далее "стягивал" круг (тоесть соединял нашу точку ( от начала движения) и точку по к которой мы прибыли) далее повторялось действие Шаг А2(уже с n-1 кол-вом заправок) до тех пор пока не останется 2 заправки. А далее снова на основании док-ва от провивного. И всё


Кстати - хамелеоны - 4 б
Побег - 3 б
А про Вазик - 5 б
(по пятибалльной шкале )

Последний раз редактировалось Poma][a; 02.10.2012 в 20:54.
Poma][a вне форума Ответить с цитированием
Старый 04.10.2012, 07:13   #29
TinMan
Форумчанин
 
Аватар для TinMan
 
Регистрация: 05.09.2011
Сообщений: 869
По умолчанию

Гм. Мне кажется, все же пора нам с тобой поиметь совесть и перелезть в личку. Хотя, не исключено, что наш с тобой белый текст читает кто-то еще, и что он находит его интересным для себя..
======= белый текст: =============
Ромаха, я (думаю, что я) понимаю, о чем ты говоришь. В математике употребляется термин "индукция" (слово "рекурсия" буквально означает "повторный вход", при этом подразумевается, что в процедуру, так что это чисто программистский термин), и это не просто термин, а точно определенное понятие (как и все в математике). С твоего позволения, я все же оставлю за собой право на сомнения в твоем доказательстве - по крайней мере до тех пор, пока я не увижу его полностью. Если не хочешь показывать его тут (хотя, мне кажется, уже пора играть в открытую)), пришли мне в личке.
======= конец белого текста ========
Ну, оценка сложности задач может быть слишком субъективна, я на своей не стану настаивать.
Предпочитаю на "ты".
TinMan вне форума Ответить с цитированием
Старый 04.10.2012, 16:39   #30
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

Карты на стол
Предположим, что нельзя найти любую такую бензоколонку, от которой мы сможем "проехать" к любой другой (разумеется с
некоторым кол-вом бензина, которое мы "найдем" на бензоколонке), тогда чтобы проехать от x1 до х2 на не хватает а1,
чтобы проехать от х2 к х3 нам не хватает а2, ....., чтобы проехать от х(n-1) к x(n) нам не хватает a(n), и наконец
чтобы проехать от x(n) до x1 нам не хватает a(n) бензина. И так сделаем вывод - чтобы проехать от x1 до x1 (по
кольцу) нам не хватит a1 + a2 + a3 + ... +a(n-1) + a(n) бензина. Но ведь известно что бензина хватает =>
противоречие => можно найти хотя бы одну точку, от которой мы сможем проехать хотя бы еще до одной заправки.
(часть 1)

И так рассмотрим обобщенный вариант решения данной задачи. Найдем точку, которую можно использовать как начальную
(от неё можно совершить хотя бы один проезд к другой заправке). Обозначим её 1. Мы можем отъехать от неё как минимум
к точке 2(при этом слив весь бензин из точки 1, у нас останется какое-то кол-во бензина, даже возможно равное 0)
Дальше возьмем, и соединим точки 1 и точки 2 в точку 1'. Вазик окажется в точке 1' c пустым баков. А бензин в точке
1' будет = бензин в точке 1 + бензин в точке 2
Дальше мы получаем задачу точно такую же задачу, НО с кол-вом параметров не n, а n-1. // Именно это и было названо рекурсией.
Решаем её методом "?" до тех пор пока не останется 1 колонки. И всё.

Теперь про по воду рекурсии и индукции, это два разных понятия.
Индукция - Метод доказательства утверждений типа: «Для каждого натурального числа n верно,
что ... ». Такое утверждение можно рассматривать как цепочку утверждений: «Для n= 1 верно, что ... », «Дляn= 2
верно, что ... », и т.д.

Вот нашел в математическом словарике слово
Редукция - сведение исходной задачи к другой, более простой
(например, что бы найти сумму внутренних углов многоугольника, можно разрезать его на треугольники).
Но всё равно другое значение.

Вот цитата Вики
Цитата:
Термин «рекурсия» используется в различных специальных областях знаний — от лингвистики до логики, но наиболее широкое применение находит в математике и информатике.
Хотя там же (в Вики) есть рекурсия в лингвистике, физике, программировании, но нет в математике. Вообщем ничего не понимаю.

(Да кстати возможно у Вас сложится не правильное мнение что я пытаюсь оправдаться, я лишь хочу найти подтверждение или опровержение существования рекурсии в математике.)

Последний раз редактировалось Poma][a; 05.10.2012 в 14:41.
Poma][a вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

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

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
игры ivan12ivan Общие вопросы по Java, Java SE, Kotlin 2 07.03.2012 09:06
игры Епгений Общие вопросы Delphi 14 14.05.2011 16:40
Моделирование человеческого разума булевской математикой Fog Свободное общение 28 12.11.2010 06:51
разработка игры "Реверси". Имеется код этой игры на С++ CD-RW Помощь студентам 0 28.03.2010 00:13