На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное DigiMania RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: shadeofgray, JoeUser
  
> покрытие прямоугольника, олимпиада
    Известно, что некоторый прямоугольник А, можно покрыть* прямоугольниками х1,х2,...хп.(прямоугольники не пересекаются друг с другом)
    такими что, длина хотя бы одной стороны у каждого из них - целое число.

    Докажите, что длина хотя бы одной стороны у А - целое число
    Сообщение отредактировано: esperanto -
    Microsoft SDE -> Intel algorithmist -> Skype SDET 2
    B.Sc - > M.Sc -> B.Psy -> Scrum Master -> Research Assistent

    https://www.youtube.com/user/igorkle1?feature=mhee
    http://igor-eta.livejournal.com/
    http://www.idea2site.com/
      А разве это не очевидно?
      Р. Беллманн: "Если вы смогли решить задачу, значит это было упражнение; иначе - это научная проблема."
        Не знаю, как насчет очевидности ответа, но мне сама фраза не понятна
        Цитата
        esperanto, 18.07.04, 13:29
        покрыть* прямоугольниками х1,х2,...хп.
        . что здесь означают символs '*' и 'x'? :unsure:
          esperanto
          Всё-таки есть существенная разница между математиками и программистами... :D
          - Свет мой зеркальце, скажи, да всю правду доложи.
          Я ль на свете всех дурнее, всех ленивей и тупее?!
          Молвит зеркальце в ответ:
          - Ты - придурок, спору нет!
          Но живет на белом свете вот таких еще две трети.
            :yes: :yes: :yes:
            :yes: :yes:
            :yes:
            :wall: >:(
            Microsoft SDE -> Intel algorithmist -> Skype SDET 2
            B.Sc - > M.Sc -> B.Psy -> Scrum Master -> Research Assistent

            https://www.youtube.com/user/igorkle1?feature=mhee
            http://igor-eta.livejournal.com/
            http://www.idea2site.com/
              Предположим что мы имеем А, с не целыми сторонами, попробуем поделить его на две части так, чтобы получилось 2 прямоугольника у которых хотябы 1 стороная целая. Мы не сможем сего сделать потому как нельзя сложить 2 целых чтобы получить нецелое. Получили противоречие, чтд :P
              Dixi et ahinam levavi.
                Цитата
                Sazabis, 29.07.04, 14:21
                Предположим что мы имеем А, с не целыми сторонами, попробуем поделить его на две части так, чтобы получилось 2 прямоугольника у которых хотябы 1 стороная целая. Мы не сможем сего сделать потому как нельзя сложить 2 целых чтобы получить нецелое. Получили противоречие, чтд

                Доказали лишь что на 2 поделить нельзя, а вдруг на 3 можно, или на 4,...
                  Цитата
                  Гость ALF, 31.07.04, 01:26
                  Доказали лишь что на 2 поделить нельзя, а вдруг на 3 можно, или на 4,...

                  Ну может неполной мат.индукцией? :)
                    хммммм. Пусть есть прям-к А со сторонами m+f, n+g (N Э m,n; 0<f<1,0<g<1) В него могут быть вписаны только прям-ки с хотя бы одной целой стороной. Пусть в одном углу стоит прям-к со сторонами (а, б) Если А - целое, то оставшаяся фигура имеет остаток стороны m+f-A, т.е. (m-A)+f, нецелую. Сторона Б может быть любой, но чтобы не плодить нецелости, ее нужно брать Y+g Y - целое, Y<=n. Далее, всю сторону (m-A)+f мы уже не можем заполнить снизу одним прям-ком, так как если мы это сделаем, на 3-ей стороне останется иррациональный кусок меньшего размера.

                    Черт :( какая-то ахинея, смысл в том, что в прям-ке останется дыра размером f*g, в которую прям-к с целой стороной не впишешь.

                    Пусть есть прям-к А (m+f, n+g) m,n целые, 0<f,g<1 тогда его площать есть (m*n)+(n*f)+(m*g)+(f*g) из которых можно выбрать только первые 3 части прям-ками с целочисленными сторонами. Если есть прям-к со сторонами (X, f*g/X) то на одной из сторон останется дыра размером (f-(f*g/X))<f, что не позволит впихнуть в нее прям-к с требуемой площадью.
                    Вообще-то задача сводится к невозможности собрать (X*a*b+1)/(a*b) из дробей 1/a и 1/b, a,b,X E N.

                    опять черт :( есть ли у кого есть еще идеи?
                    Долог путь в бессмертие... я еще вернусь.
                    Профильный скилл "Телепатия" 8%
                    ТРОЛЛЬ - Троян Разрушительный Опасный, Лучше ЛинятЬ (с) Freezing Spell
                    Прошу потестить игру.
                      Предлагаю так...

                      Дано:
                      A - прямоугольник;
                      Введем P(A) = "У A длина хотя бы одной стороны - целое число";

                      {Xi, i=1..n}
                      Xi & Xj = 0, при i <> j;
                      X1 | X2 | ... | Xn = A;

                      Доказать: P(X1) & P(X2) & ... & P(Xn) -> P(A);

                      Доказательство.

                      Выбрать прямоугольник Xi, находящийся в нижнем углу A, обозначим его KLMN.
                      Пусть M лежит внутри A и сторона KL - целая, расположена вертикально.
                      Разрежем исходный прямоугольник по прямой (LM).
                      Возьмем верхнюю часть и обозначим ее A'. Очевидно, что P(A) <-> P(A').
                      т.к. прямая (LM) может пересекать Xj тремя способами, то выполнение P(X'j) не нарушается
                      a) вдоль стороны - тривиально;
                      б) У Xj вертикальная сторона целая - из целого вычесть KL - целое = целое;
                      в) У Xj горизональная сторона целая - пересечение с (LM) не существенно.

                      Так будем резать пока не останется один цельный прямоугольник
                      (т.к. Xj-ых конечное число), покрытый единственным X'' у которого длина хотя
                      бы одной стороны целая.
                      :whistle:
                      0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                      0 пользователей:


                      Рейтинг@Mail.ru
                      [ Script Execution time: 0,1118 ]   [ 16 queries used ]   [ Generated: 23.07.19, 17:46 GMT ]