Форум PHP

Моей знакомой задали задачу:
Необходимо посчитать кол-во счасливых билетов с заданной суммой цифр, среди тех, номер которых состоит из 2*N разрядов. Счастливым является бител у которого сумма первых N цифр равна сумме N последних
Обьясняю =)
В N указываем кол-во цифр. Ищем билеты из цифрового диапозона счастливые, и проверяем на равность заданной сумму. Если сумма совпадает, выводим номер.
Пример: Сумма = 6: N = 3:
Билеты: 123123 222222 006006 и т.д.
Лично меня это в тупик поставило (спал всего два часа) но заинтриговало. Предлогайте варианты Мастера!

rand + array_sum

Не так все просто =)))
Билет имеет вид xxx xxx, где кол-во x задаеться n =))

Чёрт, там какое-то элегантное решение было, основанное на перестановках, но я его напрочь не помню :)))

Вы забыли указать что у вас ограничение во времени 1 ск. Это задача с Европейской олимпиады, 2 летней давности, я со своей командой принимал участие, кстати мы решили ее очень легко, если есть желание могу прислать исходник на Паскале :-)

http://g6prog.narod.ru/g6_1002.html решение
наверно поэтому вы ее быстро решили )

http://g6prog.narod.ru/g6_1002.html решение
наверно поэтому вы ее быстро решили )

Могу предложить более сложную задачу, мы ее решили за 15 минут :-). Есть поле, расчерченное как шахматная доска, на поле одна дырка, нора для кузнечиков. Кузнечики прыгают Г образно, как конь на шахматной доске. Вам дают исходные данные поля. На некоторых клетках поля сидят кузнечики (поле равно 1) или не сидят (поле равно 0). Ваша задача, высчитать сколько минимального времени потребуется всем кузнечикам для прихода домой. Размер поля мкс 1000х1000, время выполнения 1ск. Кстати задачу можно решить и на 10000х10000 :-)
П.С. Подсказка, нужно использовать алгоритм Волны :-)

а что значит "время выполнения 1ск"? что такое "ск"?

Опять не то =))
Пример:
Задаем Число цифр Пусть будет N=3, на ее месте может быть и 5 или 10
Задаем искомую сумму Сумма = 25
Вид билета после этого xxx-xxx (т.к. N * 2)
В итоге надо искать искомую сумму в диапозоне от 000 000 до 999 999

Эту задачу уже несколько десятилетий мусолят... выложите если несложно исходники, я подозреваю Akira-e именно на Pascal и нужно :)))

1 На php =)
2 Число задаеться и может быть больше 3-х

Если честно я неуверен, что правилно понял вопрос, но вроде бы лагоритм такой:
Считаем кол-во символов
Делем их на два.
Первую половину разбиваем по одному числу и скаладываем
Тоже самое и со второй половиной
Сравниваем
-
Или я не так понял вопрос? :)))

Ой Flash опередил меня :))))

Краткое описание решения данной задачи.
Получаем число в виде текста, потом циклом превращаем каждый символ в цифру. И конечно получаем что то вроде

$Number = '00020002';    $Count = StrLen($Number);    $Mid = $Count/2;    $Sum1 = 0;    $Sum2 = 0;    for ($i=1; $i<=$Mid; $i++) {        $Sum1 += $Number[$i];    }    for ($i=1; $i<=$Mid; $i++) {        $Sum2 += $Number[$Mid+$i];    }    if ($Sum1 == $Sum2) {      echo "Sum: ".$Sum1;    }

Как разбить текст на цифры, есть функция которая преобразует текст вроде text1, text2, text3 в массив
из трех элементов, к сожалению не помню ее имя.

П.С.
Кстати у вас очень облегченный вариант, у нас был казан диапазон и мы должны были найти все счастливые билеты! :-) А диапазон насчитывал 10 в степени 12

Боюсь вы неправильно задачу поняли:


Пример: Сумма = 6: N = 3:
Билеты: 123123 222222 006006 и т.д.

Я хотел сначало такой же алгоритм предложить . Как я понял мы задаем число N и сумму, а скрипт нам выдает все возможные варианты

Истинно так. Я не как не могу придумать решение, которое бы не подвисало систему.

Я все равно не понял задачи :)))

В общем как я понял:
Есть две переменные, они задаются пользователем, например:
$n = 3;
$sum = 6;
Скрипт должен значит вывести все номера, состоящие из $n*2 цифр (в нашем примере из 6) у которых сумма левых трех = сумме правых трех , в нашем примере 6 = 6

Ага =)) Завтра подумаю =) А то спать хочеться.

аааааааа понял, я тоже подумаю

И конечно я добавлю от себя, обязательно подумаю, как время появится а то мне сегодня сообщили что 7 зачетов надо сдавать а я уже про универ совсем забыл. :-) Как не люблю конец года! :-(

Я где-то за час вот это сочинил:

function HAPPY($n, $sum) {     if ($n<0 || $sum<0) {         echo "Аргументы не могут быть отрицательными.";         return;     }     $max = str_repeat('9', $n);     $m = array();     for ($t = 0; $t <= $max; $t++) {         for ($x = $t_sum = 0; $x <= strlen($max); $x++) {             $t_sum += substr($t, $x, 1);             if ($t_sum < $sum) continue(1);         }         if ($t_sum==$sum) $m[] = @str_repeat('0', $n - strlen($t)).$t;     }     for ($x = 0; $x < count($m); $x++) {         for ($y = 0; $y < count($m); $y++) {              echo "$m[$x] $m[$y]<br>";         }     }     echo 'всего счастливых билетов: '.pow(count($m), 2).' шт.'; }

По-моему, делает что-то похожее на заданную тему. Если N <= 4, работает довольно быстро. Для N = 5, 6 помедленнее. Для N > 6 у меня не выходит - срабатывает лимит по времени, слижком уж вариантов много выходит!

Ребята вот что мы с моим напарником нашли, первая загвоздка в том что первая часть билета должна начинается как минимум с единицы а вот вторая не обязательно. Получаем
Sum = 3; N = 4;
1002 - 0003
Так что с парами не пройдет, мы хотели сгенерировать все 4 значение числа и потом использовать для генерации 8 "значных", но как видите это заведет в тупик

Сейчас достал из куртки билетики от вчерашних поездок на автобусе. Цитирую номера:
023531
044890
0003520
Как видите, с нулей начинаются только в путь! И, кстати, могут нечётное к-во цифр иметь!

Вот мой вариант который мы сделали с моим напарником в лоб, конечно можно еще увеличить продуктивность сейчас как раз работаем на этим.

<?php   $Number = array ();   $Number = array_fill(0, $N+1, 0);   while ($Number[0] == 0) {     //proverau dannoe chislo, ravna li suma tomu chto nam nujno     $NumberSum = array_sum($Number);     if ($NumberSum == $Sum) {       for ($i=1; $i<=$N; $i++) {         echo $Number[$i];       }       echo '<br>';     }     //proverau stoit li prodoljat ili mojno proputstit     //bez etoi vstavki rabotaet 25 sekunt esli N=6 a s etoi vstavkoi 3,5 sekundi     if ($NumberSum > $Sum) {       $Number[$N] = 10;     } else {       //nelza propuskat       $Number[$N] += 1;     }     //proverau na neobkodimost uvelichit chisla     $CheckDone = False;     $i = $N;     while (!$CheckDone) {       $CheckDone = True;       if ($Number[$i]>9) {         $Number[$i] = 0;         $i -= 1;         $Number[$i] += 1;         $CheckDone = False;       }     }   } ?>

http://gesoft.org/goodtask.php?Sum=8&N=7
http://gesoft.org/goodtask.php?Sum=5&N=8

<!doctype html public "-//W3C//DTD HTML 4.01//EN"> <html>    <head>       <title>Lucky Ticket</title>       <meta http-equiv="generator" content="PHP Designer 2005" />    </head>    <body bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000"> <form action="num.php" method="POST" enctype="application/x-www-form-urlencoded"> Сумма: <input type="text" name="sum" /> <br> <br> Кол-во: <input type="text" name="num" /> <input type="submit" /> </form>    </body> </html>

<?php if (empty($sum) or empty($num)) {echo "Данные не верны"; exit;} if ($sum <= 9 or $num <= 1)  {echo "Данные не верны"; exit;} /* Проверяем возможность получения суммы из данного кол-ва чисел */ if ($sum >= (9*$num)) {echo "Данная сумма слишком велика";exit;} /* Получаем максимальное значение */ while ($i < floor($sum / 9)) {   $max[]=9;   $i++; } $k = $sum - array_sum($max); if ($k != 0) {   $max[]=$k; } if (count($max)!=$sum) {   $i=0;   while ($i <= ($num - count($max)))   {     $max[]=0;     $i++;   } } /* Получаем минимальное значение */ $min = array_reverse($max); /* Перебор для поиска суммы */ echo "Комбинации цифр <br>"; $min = implode ("",$min); $max = implode ("",$max); settype ($min,"integer"); settype ($max,"integer"); for ($i=$min;$i <= $max;$i++) {   $ar = preg_split('//',$i);   array_pop ($ar);   array_shift ($ar);   if ($sum == array_sum($ar))   {     if ($num < count($ar)) exit;     $ar = preg_split('//',$i);     array_pop ($ar);     array_shift ($ar);     for ($ii=0;$ii < ($num - count($ar));$i)     {       array_unshift ($ar, "0");     }    foreach ($ar as $index)     {       print $index;     }     echo "<br>";   }    }  ?>

По моему не плохо.

А почему "Данные не верны", когда, например, Cумма = 3 и Кол-во = 3? Или билетик "111 111" недостаточно счастливый? :))

Попробуй Кол-во = 5 и Сумма = от 10 до 18. Все числа результата начинаются с нуля. А где остальные?

Сумма слишком мала =) я специально не разрешил использовать маленькие суммы =) И по условию кол-во цифр в билете ВСЕГДА четно

Не вижу резона делать ограничение на сумму! Или это было указано в условии задачи? Кстати есть на уме еще быстрее алгоритм, по моим подсчетам он должен справится с N=20 как минимум! Но вот облом его писать! Ращение на математическом уровне :-)
Замечу что если нужно получить только количество то это облегчает задачу!
Кстати предложенный вами вариант довольно быстрый, кто-то проверял на ошибки?
П.С. Хочу уточнить что мой вариант ращения получает только половину билета, я посчитал что как получить все возможные варианты из половинок это все знают, два цикла вставленные в друг друга!

Маленькую сумму я оградил здравым смыслом =)
Сумму меньше 9 подсчитать легко. Просто делим не на 9, а на 8, 7, 6 и т.д.

Время выполнения я снизил максимально (при условии перебора).
Так же не стал выводить все возможные билеты с правильным суммарными слогаемыми, опять же из-за здравого смысла, нагрузка на сервер велика =/
Эту задачу надо писать не на php, но к моему великому сожелению других языков не знаю.
Кстати математически эту задачу не решить. Пробывал обмозговать с преподом математики =)))
Я все думаю, как написть листинг без использования перебора.
Есть у меня мысль =)
Пример: 923 - это в сумме 14.
Если из последнего слогаемого вычесть 1 и прибавить ее ко второму появиться
931. Этот ответ занести в массив.
Теперб делаем то же самое до достяжения 0. И все ответы в массив (при условии что такого числа нет в массиве, хотя дубликаты потом можно удалить)
Так проходим все слогаемые.
Не знаю будет ли это быстрее, пробывать не пытался.
PS Очень удивлен, что cheops не предложил своего варианта.

Мой математик, член моей команды, в свое время нашел формулу по которой он получал все возможные цифры сума которых и была равна искомой. Мы получали что то в этом роде
Sum=10
9,1
8,1,1
8,2,
7,1,1,1
7,2,1
7,3
и т.д.
Потом же из каждых можно очень быстро сгенерировать все возможные числа как например из 9,1 можно получить 91 или 19 если N=3 то можно еще нулики подставлять. Дело в том что мы не можем вспомнить как мы получали эти цифры (комбинацию)

А потом после этого проверка кол-ва цифр =))) Еще занемает время.

Да не проверять количество не надо, так как у вас исходно есть что из неких 5 цифр можно собрать сумму например 10, а вам нужны все 7 значение числа, тогда вы добавляете еще два 0 и генерите все возможные варианты! Это очень быстрый вариант, быстрей как мы подумали сделать не будет возможно!

Изначально дано некоторое кол-во чисел n =) Оно может принемать любое кол-во.

Изначально дано некоторое кол-во чисел n =) Оно может принемать любое кол-во.