ПОмогите пожалуйста ленивому студенту, завтра здавать идей нет.
задача такая:
имеем некоторое натуральное число N. среди всех положительных чисел, меньших или равных N, необходимо найти число с мавксимальным произведением цифр.
входное N: 1<=N<=2*10 в 9 степени.
например:
4876
выходные:
2268
Т.Е. число 4799 не происходит 4876 и емеет произведение цифр равное 4*7*9*9=2268

Здравствуйте, Аноним, Вы писали:

А> ПОмогите пожалуйста ленивому студенту, завтра здавать идей нет.
А> задача такая:
А> имеем некоторое натуральное число N. среди всех положительных чисел, меньших или равных N, необходимо найти число с мавксимальным произведением цифр.
А> входное N: 1<=N<=2*10 в 9 степени.


Путь ответ — К. Пусть самая левая (то есть самая значимая) цифра, отличающаяся у N и K находится на i-м месте. Тогда все цифры левее i-й будут равны у N и K, i-я цифра K будет равна i-й цифре N минус 1, а все остальное будет равно 9. Перебираем все i и выбираем максимум.

Здравствуйте, Аноним, Вы писали:

Не заметил, что может быть N=K. Этот случай проверяется отдельно.

Здравствуйте, Vintik_69, Вы писали:

V_>Путь ответ — К. Пусть самая левая (то есть самая значимая) цифра, отличающаяся у N и K находится на i-м месте. Тогда все цифры левее i-й будут равны у N и K, i-я цифра K будет равна i-й цифре N минус 1, а все остальное будет равно 9. Перебираем все i и выбираем максимум.

спасибо шас попробую как нибудь реализовать.

Здравствуйте, Vintik_69, Вы писали:

а не могли бы вы представить часть программы, ну я прям очень ленивый студент!!!!!

Здравствуйте, Vintik_69, Вы писали:

V_>Здравствуйте, Аноним, Вы писали:

А>> ПОмогите пожалуйста ленивому студенту, завтра здавать идей нет.
А>> задача такая:
А>> имеем некоторое натуральное число N. среди всех положительных чисел, меньших или равных N, необходимо найти число с мавксимальным произведением цифр.
А>> входное N: 1<=N<=2*10 в 9 степени.


V_>Путь ответ — К. Пусть самая левая (то есть самая значимая) цифра, отличающаяся у N и K находится на i-м месте. Тогда все цифры левее i-й будут равны у N и K, i-я цифра K будет равна i-й цифре N минус 1, а все остальное будет равно 9. Перебираем все i и выбираем максимум.

не совсем так. допустим ваше число 9200, тогда судя по этому алгоритму получится 9 * 1 * 9 * 9 = 729, а правильный ответ 8 * 9 * 9 * 9 = 5832
т.е. алгоритм примерно такой (брут форс однако):

a = 1;
for (int k = 0; k < num_digits(N); k++)
{
  x[k] = a * (digit(N, k) - 1) * pow(9, num_digits(N) - 1 - k);
  a *= digit(N, k);
}
тут имееем num_digits(N) + 1 число (x[] и a) одно из которых и есть ответ :-)

Здравствуйте, Sergey A. Sablin, Вы писали:

SAS>не совсем так. допустим ваше число 9200, тогда судя по этому алгоритму получится 9 * 1 * 9 * 9 = 729, а правильный ответ 8 * 9 * 9 * 9 = 5832
SAS>т.е. алгоритм примерно такой (брут форс однако):

Я же написал, "перебираем все i". В данном случае i == 3 тоже переберется.

Здравствуйте, Аноним, Вы писали:

А>а не могли бы вы представить часть программы, ну я прям очень ленивый студент!!!!!

Понятие "ленивый студент" коррелирует с понятием "армия"

Здравствуйте, Sergey A. Sablin, Вы писали:

SAS>

SAS>a = 1;
SAS>for (int k = 0; k < num_digits(N); k++)
SAS>{
SAS>  x[k] = a * (digit(N, k) - 1) * pow(9, num_digits(N) - 1 - k);
SAS>  a *= digit(N, k);
SAS>}
SAS>тут имееем num_digits(N) + 1 число (x[] и a) одно из которых и есть ответ :-)
SAS>

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

Здравствуйте, <Аноним>, Вы писали:

А>а не могли бы вы представить часть программы, ну я прям очень ленивый студент!!!!!

Ленивому студенту — ленивые вычисления!
Хаскелл.

-- разлагаем N на цифры (младшими разрядами вперёд)
todigits 0 = []
todigits n = (n%10) : (decimals (n/10))

fromdigits [] = 0
fromdigits x:xs = x + 10*(fromdigits xs)

-- порождаем список чисел K (представленных разложениями) вида [9,9,...,9,x-1,y,...,z] где [a,b,....,w,x,y,...,z] - разложение числа N
keys xs = key' [] xs where
    keys' nines x:xs = if x>0 then (nines++[x-1]++xs) : restkeys else restkeys where restkeys = keys' (9:nines) xs
    keys' nines [] = []

-- произведение цифр
prod [] = 1
prod x:xs = x * prod xs

-- а теперь находим максимум среди keys decimals n
maxkey ks = maxkey' 0 [] ks where
    maxkey' mp mk [] = mp
    maxkey' mp mk k:ks = let p = prod k in if p>mp then maxkey' p k ks else maxkey' mp mk ks

-- осталось применить это дело к n
findk = fromdigits.maxkey.keys.todigits

Не помню прелюдию наизусть, поэтому написал рекурсивные определения там, где можно было воспользоваться стандартными алгоритмами (например, prod = fold (*) 1). Ну и ладно, так нагляднее.
Возможно, что накосячил. Сейчас поотлаживаю...

P.S.
Это была мстя за такую нахальную просьбу.

Здравствуйте, Кодт,

Налепил на F# (CaML) без особых наворотов

(* произведение цифр числа n *)
let rec prod n = if n=0 then 1 else (n%10)*(prod (n/10))
    ;;

(* список чисел с девятками на конце, меньших n *)
let keys n =
    let rec impl m e = (* рассматриваем число m*e где e - степень десяти *)
        if m=0
            then []
            else
                let (a,b) = (m/10,m%10) in
                let tail = impl a (e*10) in
                if b<=1 (* если младший разряд = 0, то операция неприменима, а если 1 - то произведение будет равно 0 *)
                    then tail
                    else (m*e-1) :: tail
    in impl n 1
    ;;

(* в отладочных целях будем выводить полученные значения *)
let printNumber n =
    printf "%d " n;
    ()
    ;;
let printNumbers ns =
    printf "["; List.foreach ns printNumber; printf "]\n"
    ;;

let best theN =
    let theKeys = keys theN in (* построили список чисел *)
    printNumbers theKeys;
    let theProds = List.map prod theKeys in (* нашли произведения их цифр *)
    printNumbers theProds;
    let theKeysAndProds = List.combine theKeys theProds in (* построили список пар ключ:произведение *)
    let theBest =
        let bestByProd (mk,mp) (k,p) = if mp>p then (mk,mp) else (k,p) (* возвращаем пару, чьё произведение больше *)
        in
        List.fold_left bestByProd (0,0) theKeysAndProds (* находим максимум в списке пар *)
    in
    let theKey,theProd = theBest in
    printf "%d %d\n" theKey theProd; (* выводим *)
    theKey
    ;;

let _ = bestKeyAndProd 4876;;
do printf "!";;

Здесь вычисления энергичные, поэтому совершенно понапрасну мы строим 3 списка. Стоит переписать на хаскелле — и чудесным образом вместо списков получатся итерации.

— находим очередной ключ: пару (m,e) превращаем в key = m*e-1, (m',e')=(m/10,e*10)
— находим произведение его цифр
— сравниваем с ранее запомненным наилучшим результатом

Дальнейшее улучшение состоит в том, чтобы сплавить порождение ключей с нахождением произведений. Чтобы по два раза не раскладывать каждое число на цифры.
Но это уже пускай автор думает.

Здравствуйте, Аноним, Вы писали:

А> ПОмогите пожалуйста ленивому студенту, завтра здавать идей нет.
А> задача такая:
А> имеем некоторое натуральное число N. среди всех положительных чисел, меньших или равных N, необходимо найти число с мавксимальным произведением цифр.
А> входное N: 1<=N<=2*10 в 9 степени.
А> например:
А> 4876
А>выходные:
А>2268
А>Т.Е. число 4799 не происходит 4876 и емеет произведение цифр равное 4*7*9*9=2268

Лентяй. Таких не берут в космонавты

Здравствуйте, Аноним, Вы писали:

Первое что пришло в голову, привести задачу к максимизации суммы логарифмов цифр. А перебор не наш метод

Здравствуйте, adontz, Вы писали:

A>Здравствуйте, Аноним, Вы писали:

A>Первое что пришло в голову, привести задачу к максимизации суммы логарифмов цифр. А перебор не наш метод

Перебор будет присутствовать в той или иной форме. Если не согласны — докажите обратное

И по ходу дела обнаружил, что первую проверку он делает для числа n-1. Баг

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

Представим число в виде little-endian списка разрядов: N=[a0,a1,....,am] = am*10^m + ... + a1*10^1 + a0.
Нам, в общем-то, неважно, чему оно равно — будем смотреть только на разряды.

Кандидаты — это N и числа K(i=1..m) < N такие, что i их младших разрядов равны 9.
Если j младших разрядов N уже равны 9, то понятно, что это общая часть всех чисел-кандидатов, поэтому давайте сразу отбросим их. Посчитаем количество младших девяток, где-нибудь запишем и отложим в долгий ящик.

Будем считать, что a0 != 9.

Теперь давайте найдём максимальное произведение среди кандидатов N, K1, ... Ki. Очевидно, что a[i+1]*...*a[m] является общей частью, поэтому нам не нужно находить произведение старших цифр. Это значит, что наш алгоритм может быть потоковым: считываем цифры N поштучно и каждый раз выбираем между победителем предшествующего тура (к которому приписываем следующий разряд) и новым претендентом.

Пусть лучшим среди [0..i] признан кандидат j, т.е. [9,...,9,a[j]-1,a[j+1],...,a[i]]
Сравним его с Ki и посмотрим, что происходит при добавлении очередной цифры.

Pj = 9*...*9 * (a[j]-1) * a[j+1] *...* a[i-1] *  a[i]
Pi = 9*...*9 *    9     *.....................* (a[i]-1)

Раз он лучший, то Pj > Pi, т.е. (a[j]-1)*a[j+1]*...*a[i-1]*a[i] > 9*9*...*9*(a[i]-1)
Это может быть только в том случае, когда a[j+1]...a[i-1] = 9...9 (либо j+1=i) и (a[j]-1)*a[i] > 9*(a[i]-1)

Чует моё сердце, что нет нужды даже хранить Pj и Pi, чтобы определять победителя... Что, фактически, придётся делать выбор между K[m-1] и K[m]... Но на этом мозговая энергия иссякла.
Желающие могут продолжить расследование.

Здравствуйте, BlackHeretic, Вы писали:

A>>Первое что пришло в голову, привести задачу к максимизации суммы логарифмов цифр. А перебор не наш метод

Ужас! Чисто целочисленную задачу переделать в вещественную.

BH>Перебор будет присутствовать в той или иной форме. Если не согласны — докажите обратное

У меня закралось подозрение, что для исходного числа N = <abc...z> (big endian) нужно выбирать между кандидатами <(a-1)99...9> и <a(b-1)9...9>
Чтобы подтвердить эту гипотезу, нужно доказать, что
max((a-1)*9,a*(b-1))*9 >= a*b*(c-1)
для любых цифр a,b,c

Возможно, придётся особо рассматривать случаи цифр 0, 1 и 9.

Здравствуйте, Кодт, Вы писали:

К>Чтобы подтвердить эту гипотезу, нужно доказать, что
К>max((a-1)*9,a*(b-1))*9 >= a*b*(c-1)
К>для любых цифр a,b,c

Гипотеза неверна для наборов:
a=1, b=1, c>1
a=2, b=2, c=9
и других

Здравствуйте, Кодт, Вы писали:

К>У меня закралось подозрение, что для исходного числа N = <abc...z> (big endian) нужно выбирать между кандидатами <(a-1)99...9> и <a(b-1)9...9>

Контрпример:
N = 37999..98
Не существеут числа K<N, для которого произведение цифр больше, чем у N.

Здравствуйте, Аноним, Вы писали:

А что все девятки не подходят?
Ну и первмя цифра — максимально возможная.


















.