LINUX.ORG.RU
Форум — Talks  

Разомнемся

 


0

1

Не устали еще обновляться и экспертствовать в толксах? Предлагаю размяться.

Вы пришли в магазин. Там есть k видов шоколадок. А вам всего нужно купить n шоколадок (k < n). Сколько вариантов у вас есть это сделать?

Присылаете рекурсивную дрисню на хаскелях / схемах / еще чем-то - отправляетесь лечиться. Идете что-то гуглить - перестаете, все что нужно для решения и так есть при вас.

← Что лоровец думает об офшорах?
WTF? →
 ← 1 2

Сколько вариантов у вас есть это сделать?

0 потому что в этих ваших говномагазинах нет нормального шоколада с черным рисом

Deleted
()
Ответ на: комментарий от alex4321

А вот и не угадал.

И все же, отвечая на твой вопрос - неважно. Чего сдесь помнить то, выражение там очевидное.

Zaskard
() автор топика
Ответ на: комментарий от Deathstalker

Потому что я хочу от вас замкнутую формулу. Рекуррентное соотношение каждый может написать.

Zaskard
() автор топика
Ответ на: комментарий от Zaskard

Хм. так ведь задача на число сочетаний с повторениями (раз k<n). И да - если выражение в общем виде (не для конкретных значений k/n) кажется тебе очевидным - ну, либо ты хорошо его помнишь комбинаторику, либо - снимаю шляпу (что не значит того, что после некоторого количества возни я бы не вспомнил или даже вывел бы его, наверное).

alex4321 ★
()
Ответ на: комментарий от router

Читер чёртов. А ведь в самом деле - чего это я полез гуглить, во что оно развернется.

alex4321 ★
()
Ответ на: комментарий от router

Какая еще пересдача? Я сторожем работаю - тут все это знают.

Кстати, так что получится по вашей формуле для 2 и 10?

Zaskard
() автор топика
Ответ на: комментарий от router

Спуфинг уже не сторож, он сам говорил. А вот я все еще сторож.

Впрочем, это не важно все, ответ то неверный.

Zaskard
() автор топика
Ответ на: комментарий от Zaskard

Так в чём ошибка-то? В общем случае же именно так и выходит.

alex4321 ★
() 
(define (make-rat n d)
  (let ((g (gcd n d)))
    (cons (/ n g) (/ d g))))

(define (numer x)
  (car x))

(define (denom x)
  (cdr x))

;;

(define (mul x y)
  (let ((d1 (gcd (numer x) (denom y)))
        (d2 (gcd (denom x) (numer y))))
    (make-rat (* (/ (numer x) d1) (/ (numer y) d2))
              (* (/ (denom x) d2) (/ (denom y) d1)))))

;;

(define (weight x)
  (max (numer x) (denom x)))

(define (overflow? x)
  (let ((p (expt 2 64)))
    (or (>= (numer x) p)
        (>= (denom x) p))))

(define (binomial-overflows? n k)
  (define (iter result n k overflow)
    (cond ((or (= k 0) (= k n))
           (and overflow (not (overflow? result))))
          (else
           (let ((q1 (make-rat n (- n k)))
                 (q2 (make-rat (+ 1 (- n k)) k)))
             (let ((r1 (mul result q1))
                   (r2 (mul result q2)))
               (if (< (weight r1) (weight r2))
                   (iter r1 (- n 1) k (or overflow (overflow? result)))
                   (iter r2 n (- k 1) (or overflow (overflow? result)))))))))

  (iter (make-rat 1 1) n k false))

;;

(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))

;(define (filter predicate sequence)
;  (accumulate (lambda (x y)
;                (if (predicate x) (cons x y) y))
;              '()
;              sequence))

;(define (map op sequence)
;  (accumulate (lambda (x y)
;                (cons (op x) y))
;              '()
;              sequence))

;;

(define (enumerate-interval from to)
  (if (> from to)
      '()
      (cons from (enumerate-interval (+ 1 from) to))))

(define (enumerate-overflows from to)
  (filter (lambda (p)
            (not (null? (cadr p))))
          (map (lambda (n)
                 (list n
                       (filter (lambda (k)
                                 (binomial-overflows? n k))
                               (enumerate-interval 0 n))))
               (enumerate-interval from to))))

(enumerate-overflows 1 200)
Deathstalker ★★★★★
()
Ответ на: комментарий от i-rinat

Мой захвати. А заодно на джое. А то я никак велосипед один не допилю.

alex4321 ★
()
Ответ на: комментарий от Deathstalker

О, а вот и лисперы подтянулись...

Deleted
()

К примеру, очевидно что если их надо купить 10 притом что есть 2 вида шоколадок то вариантов у нас будет 11 (просто перебор по последовательности). Поэтому, для начала, попробуйте проверить ваши решения на этих числах.

Zaskard
() автор топика
Ответ на: комментарий от f1u77y

Вот у меня такое же решение. Но только сейчас я подумал что это, кажется, не захватывает еще k случаев. Могу ошибаться, очень сонный.

Zaskard
() автор топика
Ответ на: комментарий от Deathstalker

и как эта простыня поможет вычислить сочетания?

f1u77y ★★★★
()
Ответ на: комментарий от f1u77y

Ну, в любом случае там еще и просуммировать надо (когда мы не всегда используем все виды в наборе).

Zaskard
() автор топика
Ответ на: комментарий от f1u77y

Да, но это значит что 2 или более перегородки могут отображаться на одно место и это не учтено в формуле.

Zaskard
() автор топика
Ответ на: комментарий от Zaskard

ой, тогда router был прав, а я обосрался(это работает только если мы хотим, чтобы была хотя бы одна каждого вида)

эх, совсем одаунел я в математике. даже такую фигню не могу решить(правда находясь в состоянии полудрёмы), а еще на всеросе всерьёз че-то брать хотел

f1u77y ★★★★
()
Последнее исправление: f1u77y (всего исправлений: 1)
Ответ на: комментарий от f1u77y

это работает только если мы хотим, чтобы была хотя бы одна каждого вида

Почему? Если n всего, значит n+1 место для перегородки. Частей k, значит перегородок k-1. Условия «каждого вида хотя бы по одной взять» не было, так что всё норм.

i-rinat ★★★★★
()
Ответ на: комментарий от i-rinat

Условия «каждого вида хотя бы по одной взять» не было, так что всё норм.

да, поэтому как раз всё не норм, ибо в таком случае нельзя пихать 2 перегородки на одно место, а надо, чтобы было можно

f1u77y ★★★★
()
Ответ на: комментарий от Zaskard

нет, все правильно

добавляем k фиктивных шаров -> C_{n-1+k}^{k-1}, как он и написал

кстати, понял, что даже в случае, когда надо хотя бы по одной, я тоже обосрался, ибо там C_{n-1}_{k-1}

f1u77y ★★★★
()

ТС, 95% ЛОРа (как и любого другого среза общества) не умеют в комбинаторику, это всем известно. У тебя типичная формула сочетаний с повторениями (обозначу как Cp, в отличии от простых сочетаний). Т.е.:

Cp(n,k)=C(n+k-1,k)

И того в твоей задаче на примере 2-ух видов шоколадок в магазине и 10 шоколадок в корзинке покупателя имеем: n=2, k=10 (а не наоборот, как ты нас специально путаешь, чтобы был весёлый срач как про монетки в сундуках), далее получаем:

Cp(2,10)=C(2+10-1,10)=С(11,10)

Ну а С(11,10) считается элементарно по формуле: 

C(n,k)=(n!)/(k!*(n-k)!)
Таким образом в твоём примере будем иметь: 
(11!)/(10!*(11-10)!)=11!/(10!)=11)
Всем выше отписавшимся, включая ТС-а, с дикими и безумными формулами ставлю неуд и жду их на пересдаче.

peregrine ★★★★★
()
Ответ на: комментарий от peregrine

n=2, k=10 (а не наоборот,

офигенно, ты поменял обозначения, но в итоге получил ровно то же, что в авторских обозначениях получили до тебя в треде(причём написали уже 2 раза)

ставлю неуд и жду их на пересдаче

всего-то написал в тред решение(которое уже есть в треде) задачи, которую средние школьники-математики >8 класса решают как нефиг, а высокомерия будто нерешённую проблему решил

ваще ты можешь сказать, что не мне это писать, но до этого признаю, что да, я тоже обосрался, причём более смачно, чем ты

f1u77y ★★★★
()
Последнее исправление: f1u77y (всего исправлений: 1)

Сколько вариантов у вас есть это сделать?

Два варианта, 50% - 50%

Или сделать, или не сделать.

pacify ★★★★★
()
Ответ на: комментарий от alex4321

Все ли помнят формулу числа сочетаний из n по k навскидку? Не думаю

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

upcFrost ★★★★★
()
Последнее исправление: upcFrost (всего исправлений: 1)
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
 ← 1 2
← Что лоровец думает об офшорах?
Talks
WTF? →