Форум: "Основная";
Текущий архив: 2004.04.11;
Скачать: [xml.tar.bz2];
Вниз
Алгоритм определения количества "счастливых" чисел Найти похожие ветки
← →
V-Isa © (2004-03-19 17:19) [0]"Счастливым" считается число, сумма цифр в котором слева до середины равна сумме цифр справа до середины. Так, 123006 - "счастливое", т.к. 1+2+3=0+0+6, а 12306 - нет, т.к. 1+2<>0+6!
Необходим алгоритм определения количества "счастливых" чисел в заданном диапазоне. Например, необходимо определить сколько таких чисел встречается от 1234 до 56789 и т.п. Обычный перебор не подходит, так как количество разрядов в исходных данных может достигать 20 и более, а это длительный процесс.
← →
WebErr © (2004-03-19 17:25) [1]Это олимпиадная задачка по комбинаторике, клёво, что она здесь появилась! Сейчас попробую решить! ... :))))
← →
WebErr © (2004-03-19 17:26) [2]
> Обычный перебор не подходит, так как количество разрядов
> в исходных данных может достигать 20 и более, а это длительный
> процесс.
Какой к чертям перебор!!! :))))
← →
V-Isa © (2004-03-19 17:28) [3]Вот именно, просто я уже неделю пытаюсь ответ получить, а мне только говорят - попробуйте перебором!
← →
WebErr © (2004-03-19 17:30) [4]Эта задачка эквивалентна другой:
сколько пар чисел, одно от А до В, другое от C до D, таких, что сумма цифр одного равна сумме цифр другого...
← →
WebErr © (2004-03-19 17:32) [5]<A>acm.timus.ru</A>
← →
WebErr © (2004-03-19 17:37) [6]Надо разложить каждую цифру одного числа (из двух) на единицы и посмотреть, сколькими способами можно расставить между единицами n-1 перегородку, где n - количество цифр числа = длина строки div 2 (или shr 1)... Но меня смущают граничные диапазоны... :))))
← →
WebErr © (2004-03-19 17:38) [7]Надо разложить каждую цифру одного числа (из двух) на единицы и посмотреть, сколькими способами можно расставить между единицами n-1 перегородку, где n - количество цифр числа = длина строки div 2 (или shr 1)... Но меня смущают граничные диапазоны... :))))
← →
WebErr © (2004-03-19 17:44) [8]Например числа от 12345 до 76543210 это можно представить в виде пар чисел от (0012, 0045) до (7654, 3210)... Но может быть и от 12345 до 13000, тогда от (12, 00) до (13, 45) - упорядочиваем поэлементно пары! :))))
← →
Goida © (2004-03-19 17:44) [9]Переведи в строку и обрабатывай её. Наилегчайший способ :) Думаю, и рациональный. Это ведь лаба? Не так ли? Если так, то кодить за тебя здесь ни кто не будет.
← →
V-Isa © (2004-03-19 17:44) [10]Что значит перегородку. Не могли бы более подробнее? Буду признателен, если ответ вышлете на мыло. Очень надо решение!
← →
WebErr © (2004-03-19 17:45) [11]Вот я и подвёл котёнка к молоку!!! Дальше техническая часть - сам попробуй! :))))
← →
V-Isa © (2004-03-19 17:48) [12]Это не лаба, просто столкнулся с желанием любимой девушки подсчитать, сколько же...?
← →
WebErr © (2004-03-19 17:50) [13]
> Что значит перегородку
Это значит, что сумму цифр числа 123 - это 1+2+3 я представляю как 1+1+1+1+1+1 6 раз! Теперь расставляем "перегородки" (1+1+1)+(1+1)+(1) разбивая n-1 перегородкой число на n частей n=3. На мыло код слать не буду - самому тоже надо что-то сделать - это я не про себя... :))))
← →
WebErr © (2004-03-19 17:56) [14]
> Это не лаба, просто столкнулся с желанием любимой девушки
> подсчитать, сколько же...?
СВЯТОЕ! Ну тогда сам бог велел тебе немного подумать головой! Напрягись ради любимой! :))))
← →
V-Isa © (2004-03-19 17:56) [15]А как быть с числами до 10? Забивать вручную?
← →
WebErr © (2004-03-19 17:57) [16]
> А как быть с числами до 10? Забивать вручную?
???
← →
V-Isa © (2004-03-19 18:02) [17]Например, диапазон от 10 до 15... Разбили: (1,0) до (1,5)... и что? Или я чего-то не понял, сбросьте на мыло, а то уже убегаю, заранее огромное спасибо! Мастера Дельфи есть мастера, хоть намекнули, не то, что математики :-) //шутя...
← →
Goida © (2004-03-19 18:04) [18]А разве есть что-то, что можно поставить в какое-то соответствие сумму цифр одной части числа другой??? Помоему в математике такого нет. Эта задачька как раз и нужна для того, что тот кто её делает научился выделять значения десятичных разрядов... Решается только перебором. Моим способом гораздо легче.
← →
Chcnger (2004-03-19 18:05) [19]Решается с помощью динамического программирования.
Разбор етсь тут g6prog.narod.ru
Интересно как найти билеты, если их разряд 2N, где 1<N<50
← →
Chcnger (2004-03-19 18:09) [20]Мое решение задачи 1044 с acm.timus.ru (про счастливые билеты, решается при помощи дин. программирования)
{1044}
var I,K,RES,N,luck,sum,spec:longint;
a:array[0..100]of longint;
s:string;
begin
res:=0;
fillchar(a,sizeof(a),0);
readln(n);
k:= n div 2;
s:="";
for i:=1 to k do S:=s+"9";
val(s,k,res);
res:=0;
for i:=1 to k do
begin
sum:=0;
luck:=i;
for spec:=1 to n div 2 do
begin
Sum:=sum+Luck mod 10;
Luck:=Luck div 10;
end;
inc(a[sum]);
end;
for i:=1 to length(s)*9 do
begin
res:=res+ a[i]*a[i];
end;
Writeln(res+1);
end.
← →
WebErr © (2004-03-19 18:15) [21]
> Chcnger (19.03.04 18:09) [20]
> Мое решение задачи 1044 с acm.timus.ru (про счастливые билеты,
> решается при помощи дин. программирования)
О! Точно, №1044! :)))) Если не трудно скинь код ему на мыло! 8*)
← →
WebErr © (2004-03-19 18:17) [22]
> Интересно как найти билеты, если их разряд 2N, где 1<N<50
А чем случай 2N отличается от 2N+1?! Можно ведь просто выкинуть "лишнюю" среднюю цифру! :))))
← →
nikkie © (2004-03-19 19:38) [23]>V-Isa
ты каждый месяц теперь будешь этот вопрос задавать? уже на Валентинов день обсуждали :))
Страницы: 1 вся ветка
Форум: "Основная";
Текущий архив: 2004.04.11;
Скачать: [xml.tar.bz2];
Память: 0.5 MB
Время: 0.037 c
