Интересные задачи

Все о программировании под *nix
Gnida
Неотъемлемая часть форума
Сообщения: 346
Зарегистрирован: 04 апр 2004, 22:38

Интересные задачи

Сообщение Gnida »

Задачи взяты из учебника по инфарматики для 8 класса.
---
Доказать что любое целое число больше 7 можно представить в виде суммы произвидений троек и пяторок, тоесть N=3x+5y , N>7
Найти все возможные значения х и у при произвольном N
---
Дробь вида p/q представить в виде суммы дробей 1/n , например 3/7=1/3+1/11+1/231
С опытом ошибки не изчезают , а умнеют

Аватара пользователя
myst
Маньяк
Сообщения: 190
Зарегистрирован: 04 окт 2005, 15:46
Откуда: не возвращаются

Сообщение myst »

Задача №1

Доказывал, что называется, "в лоб", потому что лень думать.

Математическая индукция:
  1. Для N = 7. N = 3*1 + 5*1. Выполняется.
  2. Допустим, что для N = 3x + 5y выполняется, тогда для N+1 = 3x + 5y + 1:
    1. при x ≥ 3:
      N+1 = 3(x-3) + 5y + 3*3 + 1 =
      = 3(x-3) + 5y + 10 =
      = 3(x-3) + 5y + 5*2 =
      = 3(x-3) + 5(y+2).
      Выполняется.
    2. при x < 3 и y ≥ 1:
      N+1 = 3x + 5y + 1 =
      = 3x + 5(y-1) + 5 + 1 =
      = 3x + 5(y-1) + 6 =
      = 3x + 3*2 + 5(y-1) =
      = 3(x+2) + 5(y-1).
      Выполняется.
    3. при x < 3 и y < 1:
      (N = 3x + 5y) < 7.
Собственно больше чем на 8-ой класс не тянет.
Последний раз редактировалось myst 11 дек 2006, 12:59, всего редактировалось 1 раз.
Иными вечерами я пью, чтобы кого-нибудь не пристрелить. Это акт благотворительности. Не за что.

Gnida
Неотъемлемая часть форума
Сообщения: 346
Зарегистрирован: 04 апр 2004, 22:38

Сообщение Gnida »

Мист , засуньте это ваше теперь в програму и пасчитайте все возможные х и у при N=8432648123482854759275437534 например
С опытом ошибки не изчезают , а умнеют

Аватара пользователя
myst
Маньяк
Сообщения: 190
Зарегистрирован: 04 окт 2005, 15:46
Откуда: не возвращаются

Сообщение myst »

Опять же, прога тупая как валенок. Только для примера. Естественно, что на ооочень больших числах будет работать медленно.

Код: Выделить всё

def factor(n):
    for y in range(int((n + 1) / 5)):
        if (n – 5*y) % 3 == 0:
            x = (n – 5*y) / 3
            print n, " = 3*", x, " + 5*", y
З.Ы. переписал на Python, чтобы было понятнее :D
З.З.Ы. Надеюсь то, что для каждого y существует один и только один х такой, что N = 3x + 5y, доказывать не надо? :D
Последний раз редактировалось myst 26 ноя 2006, 22:51, всего редактировалось 1 раз.
Иными вечерами я пью, чтобы кого-нибудь не пристрелить. Это акт благотворительности. Не за что.

Аватара пользователя
myst
Маньяк
Сообщения: 190
Зарегистрирован: 04 окт 2005, 15:46
Откуда: не возвращаются

Сообщение myst »

Задача №2

Код: Выделить всё

def factor(n):
    print n, " = ",
    while p != 1:
        x = int(q / p) + 1
        print "1/", x, " + ",
        p = p*x - q
        q = q*x
    print "1/", q
Тут гораздо более интересно доказательство того, что такое разложение существует и конечно. Но это надо думать, а мне лень. ;)

Пофикшен баг: не печаталася последняя дробь ряда.
Последний раз редактировалось myst 28 ноя 2006, 14:36, всего редактировалось 1 раз.
Иными вечерами я пью, чтобы кого-нибудь не пристрелить. Это акт благотворительности. Не за что.

Gnida
Неотъемлемая часть форума
Сообщения: 346
Зарегистрирован: 04 апр 2004, 22:38

Сообщение Gnida »

для первой задачи логическое доказательство основываеца на свойствах остатка после деления любого числа на 5 , а возможные х и у находяца уже из хатябы одной пары изестных х и у , например 5*10+3*20=5(10-3)+3(20+5) так можно сильно сакратить количество циклов паходу.
Втарая задача ришение правильное , а насчет даказательства я даже и не падумал падумать :) Вобщем мист маладец
С опытом ошибки не изчезают , а умнеют

Gnida
Неотъемлемая часть форума
Сообщения: 346
Зарегистрирован: 04 апр 2004, 22:38

Сообщение Gnida »

А верную пару х и у в первой задачи можно легко найти проанализировав астатак ат деления на 5 , в общем можно ооочень бысро решать эту задачу для оооооочень больших чисел
С опытом ошибки не изчезают , а умнеют

Аватара пользователя
myst
Маньяк
Сообщения: 190
Зарегистрирован: 04 окт 2005, 15:46
Откуда: не возвращаются

Сообщение myst »

вариант, но это уже не 8-ой класс ;)
Иными вечерами я пью, чтобы кого-нибудь не пристрелить. Это акт благотворительности. Не за что.

Gnida
Неотъемлемая часть форума
Сообщения: 346
Зарегистрирован: 04 апр 2004, 22:38

Сообщение Gnida »

К сожалению эта только васьмой :)
Если тебе мист интересно , я сейчас читаю пару книжек , могу интересные задачи которые там будут сюда кидать
С опытом ошибки не изчезают , а умнеют

Аватара пользователя
myst
Маньяк
Сообщения: 190
Зарегистрирован: 04 окт 2005, 15:46
Откуда: не возвращаются

Сообщение myst »

Кидай-кидай. Тока пусть модеры это в программинг снесут.
Иными вечерами я пью, чтобы кого-нибудь не пристрелить. Это акт благотворительности. Не за что.

michael
Неотъемлемая часть форума
Сообщения: 434
Зарегистрирован: 12 апр 2004, 11:00
Откуда: г. Владивосток
Контактная информация:

Сообщение michael »

Вы помедленнее, а то не успеваешь задачу прочитать, myst ответ пишет :)

Аватара пользователя
myst
Маньяк
Сообщения: 190
Зарегистрирован: 04 окт 2005, 15:46
Откуда: не возвращаются

Сообщение myst »

Ннууу... и где продолжение?!
Иными вечерами я пью, чтобы кого-нибудь не пристрелить. Это акт благотворительности. Не за что.

Gnida
Неотъемлемая часть форума
Сообщения: 346
Зарегистрирован: 04 апр 2004, 22:38

Сообщение Gnida »

Предположим , что у нас есть весы с двумя чашами и по одной штуке гирь массой 1,3,9,3^k граммов , уравновесить груз массой М граммов на весах. Гири конечно можно засовывать и на правую и на левую чашу , как угодно
С опытом ошибки не изчезают , а умнеют

michael
Неотъемлемая часть форума
Сообщения: 434
Зарегистрирован: 12 апр 2004, 11:00
Откуда: г. Владивосток
Контактная информация:

Сообщение michael »

M представляем в троичной системе счисления, далее процедура элементарна. Массы гирь сразу наталкивают на ответ. :)

Аватара пользователя
hlamer
Увлекающийся
Сообщения: 119
Зарегистрирован: 24 фев 2006, 23:34

Сообщение hlamer »

Gnida писал(а):... я сейчас читаю пару книжек , могу интересные задачи которые там будут сюда кидать
Что за книжки из которых задачки, если не секрет ?
И сошел на него Дух Господень...
Нашел он свежую ослиную челюсть, и,
протянув руку свою, взял ее,
и убил ею тысячу человек.
Книга Судей, глава 15, стих 14, 15

Ответить