Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 142
Отношение члена любого аддитивного ряда (а ряд Фиббоначи именно такой) к предыдущему члену стремится к золотому сечению. Чем больше числа тем дольше их вычисляет компьютер. Тут всё линейно и ничего удивительного.
Нам на дифурах предподаватель когда-то рассказал байку про китов.
Исследователи китов обнаружили, что отношение длины окружности кита в самом его «широком» месте к наибольшему диаметру того же кита всегда лежит в диапазоне 3.09-3.20! Поразительный факт! Тоже тема для размышлений ;-)
Исследователи китов обнаружили, что отношение длины окружности кита в самом его «широком» месте к наибольшему диаметру того же кита всегда лежит в диапазоне 3.09-3.20! Поразительный факт! Тоже тема для размышлений ;-)
Ха-ха. Вызвали у меня радость. Видно исследователи китов не учили математику:)
Интересно, что если взять достаточно гладкий камень, то угол между максимальным и минимальным диаметром будет около 90°.
Нам препод по дискретке говорил, что в каком-то американском штате число Пи решили округлить до 3-х. Ну для простоты расчетов.
перл ужасен!
#!/usr/bin/env python
n = 0
for num in range(1000000):
st = str(num)
st = '0'*(6-len(st)) + st;
if int(st[0]) + int(st[1]) + int(st[2]) == int(st[3]) + int(st[4]) + int(st[5]):
n = n+1
print n
$ python tickets.py
55252
#!/usr/bin/env python
n = 0
for num in range(1000000):
st = str(num)
st = '0'*(6-len(st)) + st;
if int(st[0]) + int(st[1]) + int(st[2]) == int(st[3]) + int(st[4]) + int(st[5]):
n = n+1
print n
$ python tickets.py
55252
Я не претендую на оптимальный код :) Собрано на коленке.
пайтон ужасен! :-))))
— php
Кому не слабо написать короче? :-))))))
for($i=1,$s='00000'.$i,$c=0;$i<=999999;$i++,$s=sprintf('%06s',$i))
($s[0]+$s[1]+$s[2]==$s[3]+$s[4]+$s[5])&&$c++;
echo "Сумма = $c";
— php
Кому не слабо написать короче? :-))))))
ээ…
php ужасен.
php ужасен.
len([x for x in ["%06d"%x for x in range(1000000)] if sum(map(int,x[0:3])) == sum(map(int,x[3:6]))])
— нечитаемый python.
— нечитаемый python.
Ну, вторая строка все равно будет с выводом. У меня тоже фактически 1 строка в этом случае, т. к. первые две на самом деле составлюят одну.
Но у вас красивее получилось, стоит признать.
Но у вас красивее получилось, стоит признать.
в коллекцию от руби:
('000001'..'999999').inject(0){|count, i| x = i.to_s; x[0].to_i + x[1].to_i + x[2].to_i == x[3].to_i + x[4].to_i + x[5].to_i? count + 1: count }
('000001'..'999999').inject(0){|count, i| x = i.to_s; x[0].to_i + x[1].to_i + x[2].to_i == x[3].to_i + x[4].to_i + x[5].to_i? count + 1: count }
perl, просто perl
perl -le 'print scalar grep { my @t = split //, $_; $t[0]+$t[1]+$t[2] == $t[3]+$t[4]+$t[5] } map { sprintf( "%06d", $_ ) } (0..999999);'
perl -MList::Util=sum -le 'print scalar grep { my @t = split //, $_; sum( @t[0..2] ) == sum( @t[4..5] ) } map { sprintf( "%06d", $_ ) } (0..999999);'
perl -le 'print scalar grep { $_ % 10 + $_/10 % 10 + $_/100 % 10 == $_/1000 % 10 + $_/10000 % 10 + $_/100000 % 10 } (0..999999);'
perl -le 'print scalar grep { my @t = split //, $_; $t[0]+$t[1]+$t[2] == $t[3]+$t[4]+$t[5] } map { sprintf( "%06d", $_ ) } (0..999999);'
perl -MList::Util=sum -le 'print scalar grep { my @t = split //, $_; sum( @t[0..2] ) == sum( @t[4..5] ) } map { sprintf( "%06d", $_ ) } (0..999999);'
perl -le 'print scalar grep { $_ % 10 + $_/10 % 10 + $_/100 % 10 == $_/1000 % 10 + $_/10000 % 10 + $_/100000 % 10 } (0..999999);'
perl -MList::Util=sum -le 'print scalar grep { my @t = split //, $_; sum( @t[0..2] ) == sum( @t[4..5] ) } m(«000000»..«999999»);'
Для perl это непозволительно длинные решения! :) Предлагаю так:
Короче пока не придумал.
$ perl -e 's|(?=.)|$a++%6>2?"+":"-"|ge,$b+=!eval for"0"x6..9x6;print$b' 55252
Короче пока не придумал.
два решения, не претендующие на краткость, скорее на некоторую «оптимальность» алгоритма:
первое «лобовое» решение, которое возникло сразу во время чтения статьи
второе решение, которое возникло сразу после завершения
второе решение требует 56252 итерации для нахождения 55252 чисел :)
первое «лобовое» решение, которое возникло сразу во время чтения статьи
#!/usr/bin/perl -w
use strict;
my @summa = ();
for my $i ( 0 .. 999 ) {
push @summa, summa($i);
}
for my $i ( 0 .. $#summa ) {
for my $j ( 0 .. $#summa ) {
printf "%03d%03d\n", $i, $j if $summa[$i] == $summa[$j];
}
}
sub summa
{
my $x = shift;
my $s = 0;
while ( $x ) {
$s += $x % 10;
$x = int($x / 10);
}
return $s;
}
второе решение, которое возникло сразу после завершения
#!/usr/bin/perl -w
use strict;
my %summa = ();
for my $i ( 0 .. 999 ) {
push @{ $summa{summa($i)} }, $i;
}
for my $x ( sort { $a <=> $b } keys %summa ) {
my @x = @{ $summa{$x} };
for my $i ( @x ) {
for my $j ( @x ) {
printf "%03d%03d\n", $i, $j;
}
}
}
sub summa
{
my $x = shift;
my $s = 0;
while ( $x ) {
$s += $x % 10;
$x = int($x / 10);
}
return $s;
}
второе решение требует 56252 итерации для нахождения 55252 чисел :)
Для вывода всех «счастливых номеров» второе решение похоже оптимально (лучше никак не сделать). Можно только записать его в коротком golf-style:
Но если задача только посчитать их количество — то легко можно обойтись 1000 с небольшим итераций. См ниже в комментариях:
$i=$_,s//+0x/gc,push@{$a[eval]},$i for"000"..9x3;map{for$x(@$_){print"$x$_\n"for@$_}}@aНо если задача только посчитать их количество — то легко можно обойтись 1000 с небольшим итераций. См ниже в комментариях:
s//+0x/gc,$a[eval]++for 0..999;$s+=$_*$_ for@a;print$s
«Кому не слабо написать короче?» — это опасный призыв ;)
Ваш вариант для php можно немного сократить:
(или еще на 1 символ, если забить на warning)
Может можно и короче, но я не знаток php. На perl, например, можно это же решение «в лоб» реализовать сильно короче:
Ваш вариант для php можно немного сократить:
for($i=1000000;$i||die("$c");$s=sprintf("%06s",--$i),$s[0]+$s[1]+$s[2]-$s[3]-$s[4]-$s[5]||@$c++);(или еще на 1 символ, если забить на warning)
Может можно и короче, но я не знаток php. На perl, например, можно это же решение «в лоб» реализовать сильно короче:
s|(?=.)|$a++%6>2?"+":"-"|ge,$b+=!eval for"0"x6..9x6;print$b
Да, вы неплохо сократили пример, но есть одна ошибка. Операция || выполнится раньше минуса, и все будет работать не верно. Вот так павильно:
Или в вашем придется ставить скобки на выражение $s[0]+$s[1]+$s[2]-$s[3]-$s[4]-$s[5].
for($i=1000000;$i||die("$c");$s=sprintf('%06s',--$i),$s[0]+$s[1]+$s[2]-$s[3]-$s[4]-$s[5]or@$c++);
Или в вашем придется ставить скобки на выражение $s[0]+$s[1]+$s[2]-$s[3]-$s[4]-$s[5].
Я, конечно, php плохо знаю — но не настолько :) В php, как и в большинстве схожих языков, у логических операций приоритет ниже, чем у сложения-вычитания.
Но когда я писал, я не смотрел в документацию — я просто всегда проверяю подобные куски кода, прежде чем опубликовать. Поэтому не поверьте, а проверьте — все будет работать верно! ;)
Но когда я писал, я не смотрел в документацию — я просто всегда проверяю подобные куски кода, прежде чем опубликовать. Поэтому не поверьте, а проверьте — все будет работать верно! ;)
А, это моя тупая ошибка. Я проверил на самом деле с самого начала, но с той лишь разницей, что у меня было $s[0]+$s[1]+$s[2]==$s[3]+$s[4]+$s[5]||@$c++ — поэтому не сработало. Я еще очень удивился этому, т. к. на самом деле должно было. Поэтому и решил, что || выполнился раньше.
Вощем, да — я стормозил.
Вощем, да — я стормозил.
А я могу так:
Проверено, работает.
for(;$i<1000;$i++,$s="".$i)$a[$s[0]+$s[1]+$s[2]]++;foreach($a as $i)$k+=$i*$i;echo $k;
Проверено, работает.
print «55252»; // :)
ну коль уж пошла такая пьянка…
(я имею ввиду, что наши коды здесь просто ужасны вообще в силу своей тормознутости, ибо тут все стремятся сейчас абы их код был короче, ане оптимальней)
ловите:
n,s=0,'000000'
while s.size
(я имею ввиду, что наши коды здесь просто ужасны вообще в силу своей тормознутости, ибо тут все стремятся сейчас абы их код был короче, ане оптимальней)
ловите:
n,s=0,'000000'
while s.size
черт, опять забыл про угловые скобки… ..(
n,s=0,'000000'
while s.size<7
s.succ!
n+=1 if s[0]+s[1]+s[2]==s[3]+s[4]+s[5]
end
p n
n,s=0,'000000'
while s.size<7
s.succ!
n+=1 if s[0]+s[1]+s[2]==s[3]+s[4]+s[5]
end
p n
Если бы видели результат компиляции вашего кода, то пришли в ужас. У вас пожалуй рекорд по пессимизации кода. А можно было вот так.
import time
tm = time.time()
cnt = 0
for L1 in range(10):
for L2 in range(10):
for L3 in range(10):
for R1 in range(10):
for R2 in range(10):
for R3 in range(10):
if L1+L2+L3==R1+R2+R3:
cnt = cnt+1
#end
#end
#end
#end
#end
#end
#end
print ("cnt = ", cnt, " time = ", time.time() - tm, " sec")
Я на этой задачке в школе на олимпиаде завалился, так же как и вы сделал все неоптимальным методом, а оказалось что некоторые преподаватели своим ученикам рассказывали о более продуктивных методах решений данной задачи.
Да, всего их около 540 Кб (http://heel.org.ua/stuff/lucky_tickets.php)
«жертвы метрополитена» наверное всю жизнь их жрать будут ;)
мне кажется это всё контроллёры придумали чтобы не скучно работать было — каждый раз цирк и почти гарантированная эффективность ;) а для жертвы приключение ;)
если учесть что есть как минимум два метода расчёта и народ не всегда правильно считает — то скучно не было ;)
+
semachki.narod.ru/txt/bilet.htm
никогда не жрал и жрать не буду, со стороны это так… меня больше интересовали автоматы по продаже билетов, где сверху прозрачная часть корпуса и через щель в ней кидаешь монетки на резиновую дорожку с разделителями, крутишь ручку чтобы вылезли билеты и видно как внутри двигается резинка-коврик, монетки как лежали на ней так и лежат (те никакого процесса над ними не происходит) но ты уже получил билеты — кажется это и был комунизм ;)
мне кажется это всё контроллёры придумали чтобы не скучно работать было — каждый раз цирк и почти гарантированная эффективность ;) а для жертвы приключение ;)
если учесть что есть как минимум два метода расчёта и народ не всегда правильно считает — то скучно не было ;)
+
semachki.narod.ru/txt/bilet.htm
никогда не жрал и жрать не буду, со стороны это так… меня больше интересовали автоматы по продаже билетов, где сверху прозрачная часть корпуса и через щель в ней кидаешь монетки на резиновую дорожку с разделителями, крутишь ручку чтобы вылезли билеты и видно как внутри двигается резинка-коврик, монетки как лежали на ней так и лежат (те никакого процесса над ними не происходит) но ты уже получил билеты — кажется это и был комунизм ;)
А я до сих пор не знаю как считать счастливые билетики, как не смешно это может звучит:) Раньше меня это особо не интересовало, а потом как-то пересели на магнитные и я и не помню таких билетов.
Весели одно время в маршрутках, встречаются часто за городом где-то, а так и не вижу их толком. Вообще думал одно время, что таких больше не выпускают:)
Но номера есть везде, даже на магнитных, а как понять счастливый он или нет не знаю до сих пор… Не расскажите?
Весели одно время в маршрутках, встречаются часто за городом где-то, а так и не вижу их толком. Вообще думал одно время, что таких больше не выпускают:)
Но номера есть везде, даже на магнитных, а как понять счастливый он или нет не знаю до сих пор… Не расскажите?
Сумма первой тройки цифр должна быть равна сумме второй тройки
это нормально
в статье ссылка на wiki — там три варианта счёта:
Счастливость» билета можно определить несколькими методами. Наибольшее распространение получили три из них:
1) Московский — если на автобусном билете напечатано шестизначное число, и сумма первых трех цифр равна сумме последих трех, то этот билет считается счастливым.
2) Ленинградский (менее распространённый) — если сумма чётных цифр билета равна сумме нечётных цифр билета, то билет считается счастливым (в статье журнала «Квант» именно этот способ назван «московским»).
3) Некоторые люди считают, что если арифметический квадратный корень из суммы шести цифр номера билета есть целое число, то билет также является счастливым. Количество таких билетов с шестизначными номерами равно 99153.
пластик не жри ;)
в статье ссылка на wiki — там три варианта счёта:
Счастливость» билета можно определить несколькими методами. Наибольшее распространение получили три из них:
1) Московский — если на автобусном билете напечатано шестизначное число, и сумма первых трех цифр равна сумме последих трех, то этот билет считается счастливым.
2) Ленинградский (менее распространённый) — если сумма чётных цифр билета равна сумме нечётных цифр билета, то билет считается счастливым (в статье журнала «Квант» именно этот способ назван «московским»).
3) Некоторые люди считают, что если арифметический квадратный корень из суммы шести цифр номера билета есть целое число, то билет также является счастливым. Количество таких билетов с шестизначными номерами равно 99153.
пластик не жри ;)
Я уже писал в комментарии идею решения задачи про счастливые билетики методом динамического программирования. habrahabr.ru/blogs/i_am_clever/40036/#comment_970933
Вообще, если честно, не понимаю, какой смысл делать на Хабре пост про программу уровня школьника-восьмиклассника?
Вообще, если честно, не понимаю, какой смысл делать на Хабре пост про программу уровня школьника-восьмиклассника?
А вы уверены, что билеты начинются с 000 000? Мне почему то казалось, что с 100 000, ибо ниразу в жизни не видел билет начинающийся на 0.
брутфорс… какой ужас… люди совершенно разучились думать! умножать и делить в уме, делая пометки ручкой на бумаге…
0: 000: 1: 1: 1
1: 001: 3: 3: 9
2: 002 011: 3+3: 6: 36
3: 003 012 111: 3+6+1: 10: 100
4: 004 013 022 112: 3+6+3+3: 15: 225
5: 005 014 023 113 122: 3+6+6+3+3: 21: 441
6: 006 015 024 033 114 123 222: 3+6+6+3+3+6+1: 28: 784
7: 007 016 025 034 115 124 133 223: 3+6+6+6+3+6+3+3: 36: 1296
8: 008 017 026 035 044 116 125 134 224 233: 3+6+6+6+3+3+6+6+3+3: 45: 2025
9: 009 018 027 036 045 117 126 135 144 225 234 333: 3+6+6+6+6+3+6+6+3+3+6+1: 55: 3025
10: 019 028 037 046 055 118 127 136 145 226 235 244 334: 6+6+6+6+3+3+6+6+6+3+6+3+3: 63: 3969
11: 029 038 047 056 119 128 137 146 155 227 236 245 335 344: 6+6+6+6+3+6+6+6+3+3+6+6+3+3: 69: 4761
12: 039 048 057 066 129 138 147 156 228 237 246 255 336 345 444: 6+6+6+3+6+6+6+6+3+6+6+3+3+6+1: 73: 5299
13: 049 058 067 139 148 157 166 229 238 247 256 337 346 355 445: 6+6+6+6+6+6+3+3+6+6+6+3+6+3+3: 75: 5625
14: 059 068 077 149 158 167 239 248 257 266 338 347 356 446 455: 6+6+3+6+6+6+6+6+6+3+3+6+6+3+3: 75: 5625
10+136+666+2080+5050+8730+10924=812+7130+19654=7942+19654=20596 *2=41192 +5625= 45817 -1=45816
ну вот исписал бы отсилы пол-листа, и без никаких формул из комбинаторики
да, погрешность в 20%, но мне бы немного усталости с глаз, да в руки тетрадь, ане notepad, и всё прекрасно считается за 10минут
1: 001: 3: 3: 9
2: 002 011: 3+3: 6: 36
3: 003 012 111: 3+6+1: 10: 100
4: 004 013 022 112: 3+6+3+3: 15: 225
5: 005 014 023 113 122: 3+6+6+3+3: 21: 441
6: 006 015 024 033 114 123 222: 3+6+6+3+3+6+1: 28: 784
7: 007 016 025 034 115 124 133 223: 3+6+6+6+3+6+3+3: 36: 1296
8: 008 017 026 035 044 116 125 134 224 233: 3+6+6+6+3+3+6+6+3+3: 45: 2025
9: 009 018 027 036 045 117 126 135 144 225 234 333: 3+6+6+6+6+3+6+6+3+3+6+1: 55: 3025
10: 019 028 037 046 055 118 127 136 145 226 235 244 334: 6+6+6+6+3+3+6+6+6+3+6+3+3: 63: 3969
11: 029 038 047 056 119 128 137 146 155 227 236 245 335 344: 6+6+6+6+3+6+6+6+3+3+6+6+3+3: 69: 4761
12: 039 048 057 066 129 138 147 156 228 237 246 255 336 345 444: 6+6+6+3+6+6+6+6+3+6+6+3+3+6+1: 73: 5299
13: 049 058 067 139 148 157 166 229 238 247 256 337 346 355 445: 6+6+6+6+6+6+3+3+6+6+6+3+6+3+3: 75: 5625
14: 059 068 077 149 158 167 239 248 257 266 338 347 356 446 455: 6+6+3+6+6+6+6+6+6+3+3+6+6+3+3: 75: 5625
10+136+666+2080+5050+8730+10924=812+7130+19654=7942+19654=20596 *2=41192 +5625= 45817 -1=45816
ну вот исписал бы отсилы пол-листа, и без никаких формул из комбинаторики
да, погрешность в 20%, но мне бы немного усталости с глаз, да в руки тетрадь, ане notepad, и всё прекрасно считается за 10минут
Я смотрю в Новосибирске самые счастливые билеты :)
помню свой первый «компьютер» 8битная приставка сюбор, там был интерпретатор языков G-BASIC и F-BASIC, на нем в 8м классе я расчитывал эту задачку. решалась задачка 2мя способами: вложенными циклами и с помощью массива. точный результатов не помню, но помню что меня удивило что вероятность получить счастливый билетик не так уж и мала :)
теперь я смело могу сказать что BASIC ужасен, причем во всех своих проявлениях :)
теперь я смело могу сказать что BASIC ужасен, причем во всех своих проявлениях :)
Ага, а теперь в 1000 раз быстрее.
#include <stdio.h>
#include <memory.h>
void main()
{
int dynamic_proramming_rules[27], answer = 0; //coz 27 is max sum of nubers in [1..999]
memset(dynamic_proramming_rules,0,sizeof(dynamic_proramming_rules));
for (int i=1; i<=999; ++i) {
++dynamic_proramming_rules[i/100+(i%100/10)+(i%10)-1];
}
for (int i=0; i<27; ++i) {
answer += dynamic_proramming_rules[i] * dynamic_proramming_rules[i];
}
printf("%i", answer);
}А причем здесь dynamic_proramming?
Наверно для пафоса.
Я поясню. Наше шестизначное число разбивается на две триады. В первой триаде мы подсчитываем распределение сумм. Во второй — мы то же самое не делаем, а используем уже подсчитанное распределение (т. к. они одинаковы). Это и есть динамическое программирование. Пусть на уровне инфузории туфельки, но оно. :)
Такой код больже похож на ДП
#include #define forn(i, n) for(int i = 0; i < int(n); ++i)
#define SQR(a) ((a) * (a))
using namespace std;
int main(){
nt true_dynamic_proramming_rules[4][28], ans = 0;
memset(true_dynamic_proramming_rules, 0, sizeof(true_dynamic_proramming_rules));
true_dynamic_proramming_rules[0][0] = 1;
forn(q, 3)
forn(i, 19) forn(j, 10)
true_dynamic_proramming_rules[q + 1][i + j] += true_dynamic_proramming_rules[q][i];
forn(i, 28) ans += SQR(true_dynamic_proramming_rules[3][i]);
cout << ans;
return 0;
}
#include #define forn(i, n) for(int i = 0; i < int(n); ++i)
#define SQR(a) ((a) * (a))
using namespace std;
int main(){
nt true_dynamic_proramming_rules[4][28], ans = 0;
memset(true_dynamic_proramming_rules, 0, sizeof(true_dynamic_proramming_rules));
true_dynamic_proramming_rules[0][0] = 1;
forn(q, 3)
forn(i, 19) forn(j, 10)
true_dynamic_proramming_rules[q + 1][i + j] += true_dynamic_proramming_rules[q][i];
forn(i, 28) ans += SQR(true_dynamic_proramming_rules[3][i]);
cout << ans;
return 0;
}
А у нас в универе на базах данных нужно было решить эту задачу с помощью SQL, причем не используя таблиц. Извините что такой динный коммент, хабру бы не помешала фича заключающая код в бокс со скроллами (просветите если есть). MySQL 5.0:
SELECT COUNT(T1.R1) AS "Всего счастливых билетов"
FROM
(SELECT 0 R6 UNION
SELECT 1 UNION
SELECT 2 UNION
SELECT 3 UNION
SELECT 4 UNION
SELECT 5 UNION
SELECT 6 UNION
SELECT 7 UNION
SELECT 8 UNION
SELECT 9) `T6`,
(SELECT 0 R5 UNION
SELECT 1 UNION
SELECT 2 UNION
SELECT 3 UNION
SELECT 4 UNION
SELECT 5 UNION
SELECT 6 UNION
SELECT 7 UNION
SELECT 8 UNION
SELECT 9) `T5`,
(SELECT 0 R4 UNION
SELECT 1 UNION
SELECT 2 UNION
SELECT 3 UNION
SELECT 4 UNION
SELECT 5 UNION
SELECT 6 UNION
SELECT 7 UNION
SELECT 8 UNION
SELECT 9) `T4`,
(SELECT 0 R3 UNION
SELECT 1 UNION
SELECT 2 UNION
SELECT 3 UNION
SELECT 4 UNION
SELECT 5 UNION
SELECT 6 UNION
SELECT 7 UNION
SELECT 8 UNION
SELECT 9) `T3`,
(SELECT 0 R2 UNION
SELECT 1 UNION
SELECT 2 UNION
SELECT 3 UNION
SELECT 4 UNION
SELECT 5 UNION
SELECT 6 UNION
SELECT 7 UNION
SELECT 8 UNION
SELECT 9) `T2`,
(SELECT 0 R1 UNION
SELECT 1 UNION
SELECT 2 UNION
SELECT 3 UNION
SELECT 4 UNION
SELECT 5 UNION
SELECT 6 UNION
SELECT 7 UNION
SELECT 8 UNION
SELECT 9) `T1`
WHERE T6.R6+T5.R5+T4.R4=T3.R3+T2.R2+T1.R1;
порадовало
Вот это жесть.
Я переложил ваш запрос на Оракл. Стало несколько короче.
Здесь для генерации чисел от 0 до 9 используется цикл с 10 итерациями: connect by level <= 10. Таблицы не используются, если не считать dual за таблицу.
select count(*) as "Всего счастливых билетов" from (select rownum-1 R6 from dual connect by level <= 10), (select rownum-1 R5 from dual connect by level <= 10), (select rownum-1 R4 from dual connect by level <= 10), (select rownum-1 R3 from dual connect by level <= 10), (select rownum-1 R2 from dual connect by level <= 10), (select rownum-1 R1 from dual connect by level <= 10) where R1+R2+R3=R4+R5+R6;
Здесь для генерации чисел от 0 до 9 используется цикл с 10 итерациями: connect by level <= 10. Таблицы не используются, если не считать dual за таблицу.
Перл ужасен, да и вообще надо использвать более прогрессивные методы.
Ведь число счастливых билетов есть суть интеграл:
1/pi * int( (sin(5x)/sin(x/2) )6,0,pi )
Далее пишем простой код.
вычитаем 1, поскольку 1 билет (000000) нам не интересен, а 0,2 это погрещность при интегрировании. Если нужно более точно, то можно воспользоваться методом «3/8», он дает приблежение как четвертая степень, а не как вторая.
Ведь число счастливых билетов есть суть интеграл:
1/pi * int( (sin(5x)/sin(x/2) )6,0,pi )
Далее пишем простой код.
#include <iostream>
#include <math.h>
double pi = 3.1415926535897932384626433832795028841971693993751;
double f(double arg)
{
return 1/pi * pow(sin(arg*5)/sin(arg/2),6);
}
int _tmain(int argc, _TCHAR* argv[])
{
const int N=15;
double knots[N],values[N];
for(int i=0;i<N;i++)
{
knots[i] = i*pi/N + (i-N/2)*1e-7;
values[i] = f(knots[i]);
}
double result=0;
for(int i=1;i<N;i++)
result+=(values[i]+values[i-1]) / 2 * (knots[i] - knots[i-1]);
std::cout<<result << '\n';
return 0;
}получаем 55252,2 вычитаем 1, поскольку 1 билет (000000) нам не интересен, а 0,2 это погрещность при интегрировании. Если нужно более точно, то можно воспользоваться методом «3/8», он дает приблежение как четвертая степень, а не как вторая.
определять pi это велосипед :)
И далее заменяете все вхождения double pi на M_PI
#define _USE_MATH_DEFINES #include <math.h>
И далее заменяете все вхождения double pi на M_PI
#define M_PI 3.14159265358979323846
Ну еще и интегрирование трапецией тот еще велосипет. Наверняка есть либы, в которых это все давно написано.
Целью было показать альтернативный метод вычисления, который скорее всего будет быстрее, чем любой перебор.
Впрочем каюсь, каюсь.
Целью было показать альтернативный метод вычисления, который скорее всего будет быстрее, чем любой перебор.
Впрочем каюсь, каюсь.
Сдаюсь, я не смог сравнить ваш и #мой (ДП) код выше — они оба выполняются за 0 тиков :)
Действительно, велосипед :)
Прежде, чем использовать прогрессивные методы их нужно еще и доказать:)
В статье приведена очень занимательная ссылка. Там этот (и не только этот) метод обосновывается. Вообще эта ссылка — самое полезное, что есть в статье, IMHO :)
См. доказательство тут: http://www.ega-math.narod.ru/Quant/Tickets.htm#A2
Осталось решить эту задачу шаблонами С++ сразу на этапе компиляции, как завещал Великий и Ужасный Александреску ;-)
for (i1=0, i1<=9,i1++)
for (i2=0, i2<=9,i2++)
for (i3=0, i3<=9,i3++)
for (i4=0, i4<=9,i4++)
for (i5=0, i5<=9,i5++)
for (i6=0, i6<=9,i6++)
if (i1 + i2 + i3) == (i4 + i5 + i6) {....}
может, как-то так? или кто-то в каментах уже писал про подобное?
for (i2=0, i2<=9,i2++)
for (i3=0, i3<=9,i3++)
for (i4=0, i4<=9,i4++)
for (i5=0, i5<=9,i5++)
for (i6=0, i6<=9,i6++)
if (i1 + i2 + i3) == (i4 + i5 + i6) {....}
может, как-то так? или кто-то в каментах уже писал про подобное?
Кто говорил что билета 000000 не существует? Вот вам моя гордость. Единственный случай, когда два счастливых билета идут подряд.
Ога! Вы кондуктор?
Хм :) Каюсь, не знал!
круто
Везет же людям!
Почти 54 метра рулончик то будет (:
Wow!!!
Stack Overflow :)
первый счастливый билет 1001)
а почему не 0110?
а почему не 0110?
Спасибо за ссылку на статьи из «Кванта».
«Счастливые» билетики собираю )). Надеюсь, теперь процесс их нахождения будет проще =).
Посчитал количество билетов типа «встреча» (суммы отличаются на единицу) и «письмо» (отличаются на 2). «Встреча» — 109494 билетов, «письмо» — 106524 билетов. В итоге примерно каждый 4-ый билет привносит немного позитива в нашу жизнь :)
А ещё можно ввести «коэффициент счастливости» билета — пусть это будет 1 — (abs(сумма_первых_трех_цифр — сумма_последних_трех_цифр) / 27). Тогда у счастливых билетов «коэффициент счастливости» будет равен 1, у «встречи» — 26/27, у «письма» — 25/27. Теперь можно напридумывать названий для остальных значений и подобрать для себя удобный коэффициент исходя из желаемой вероятности получить «почти счастливый» билет. Можно ещё распределение посчитать, в общем будет чем себя занять на пару дней.
Ещё интересно получить условные плотности этого распределения при фиксированных первых цифрах, например :) Так как если исходить из предположения о том, что номера выдаются подряд, то эти цифры будут меняться редко, стало быть, есть возможность оценить свои шансы на сегодняшний день, зная цифры во вчерашнем билете.
Мне казалось, что в Москве такие билетики уже давно не используются, нет?
Вспомнилось:
«Не существует ни одного числа, которое не обладало бы какими-нибудь необычными свойствами.»
(М. Гарднер. От мозаик Пенроуза к надёжным шифрам)
«Не существует ни одного числа, которое не обладало бы какими-нибудь необычными свойствами.»
(М. Гарднер. От мозаик Пенроуза к надёжным шифрам)
билетов, счастливых по новосибирски, ровно 670 штук (см. Статью «кванта»). А полусчастливых (когда суммы каких либо двоек равны) уже 1990!
Я счастливый билет всегда на выходе съедаю.
Я всё жду, когда кто-нить из вас на брейнфаке напишет код.
++++++++++[->++++++++++[->++++++++++[-><[->+>+<<]>[-<+>]<<[->>+>+<<<]>>[-<<+>>]<<<[->>>+>+<<<<]>>>[-<<<+>>>]>[[->>>>>>>>>>>>>>>>>>>>>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<<<<<<<<<<]>[-<+>]<+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>>>>>>>>>>>>]<<<<<<<<<<<<<<<<<<<<<<<<<<<<-]>+<<[[->+<]>-<<]<]<]<]>>>>>[[-<+<+>>]<[-<[-<+<+>>]<[->+<]>>]<[-]>>>]<<<<<<[>[-<+>]<<]>.
всю ночь пыхтел ..)
всю ночь пыхтел ..)
В 10 классе у меня на олимпиаде по математике такая задача была
у меня в кошельке до сих пор лежат билеты еще с 10го и 11 класов школы, когда ездаили на занятия по УПК — мне всегда доставался счастливый билет. Накопилось штук 50 8)
у меня прямо передо мной сейчас лежит билетик с номером 011110, (на работе в понедельник буду, отсканирую) который я получил в самый неудачный день в моей жизни, причем я совершенно случайно потратил на него последний пятак, и уехал на этом дурацком троллейбусе не туда куда мне нужно… на этом неудачи закончились правда…
В маршрутке Медведково — Тарасовка выдают за один проезд сразу 4 билета: на 17 рублей + 10 рублей + 10 рублей + 3 рубля = на сумму 40 рублей
В Ростове-на-Дону мне рассказывали про парня, у которого дома висела картина — спинка от старого троллейбусного сиденья, сплошь обклеенная _счастливыми_ билетиками.
Называлась инсталляция просто и незатейливо: «Счастье» :-)
Называлась инсталляция просто и незатейливо: «Счастье» :-)
еще одно решение на перле, чуть подлиннее предложенных, зато выглядит забавно:
print 0+grep{/(.)(.)(.)(.)(.)(.)/ && $1+$2+$3==$4+$5+$6}'0'x6..1x6
В итоге все начали мериться пиписьками, у кого код меньше :) Не ожидал ))
Формулу придумать не удалось но кое-что наваял:
Здесь k — это сумма цифр, n — количество цифр в половинке билета.
Количество возможных комбинаций для конкретной суммы k вычисляется по формуле:
Nn(k) = Nn(k-1) + Nn-1(k) — Nn-1(k-10).
Вообще говоря это справедливо для ячеек, выделенных голубым цветом, ибо для остальных одно из значений в формуле не существует (равно нулю).
Так, для оранжевых ячеек это будет:
Nn(k) = Nn(k-1) + Nn-1(k),
а для жёлтых:
Nn(k) = Nn(k-1) — Nn-1(k-10).
Например, количество всевозможных комбинаций для «трехзначных» билетов сумма цифр в которых равна 12, будет равно:
73 = 69 + 7 — 3.
Количество всех билетов вычисляется как сумма квадратов полученных значений для всех k.
Здесь k — это сумма цифр, n — количество цифр в половинке билета.
Количество возможных комбинаций для конкретной суммы k вычисляется по формуле:
Nn(k) = Nn(k-1) + Nn-1(k) — Nn-1(k-10).
Вообще говоря это справедливо для ячеек, выделенных голубым цветом, ибо для остальных одно из значений в формуле не существует (равно нулю).
Так, для оранжевых ячеек это будет:
Nn(k) = Nn(k-1) + Nn-1(k),
а для жёлтых:
Nn(k) = Nn(k-1) — Nn-1(k-10).
Например, количество всевозможных комбинаций для «трехзначных» билетов сумма цифр в которых равна 12, будет равно:
73 = 69 + 7 — 3.
Количество всех билетов вычисляется как сумма квадратов полученных значений для всех k.
А я раньше играл в «сотню» с этими билетиками. Суть — расставить арифметические знаки между цифрами так, чтобы в результате получилось сто. Например, попался билет 516233. Решение: 5 * 16 + 23 — 3 = 100. Весьма занимательно и полезно с утра для пробуждения по дороге :)
Не в тему про билеты, но в тему про интересные занятия, когда делать нечего.
Вероятно, вы видели игрушку
users.cosmostv.by/rmaksim/coding/yours40moves/yours40moves.html
где нужно переставить шарики за 40 ходов.
Так вот первое, что мне пришло в голову (и было реализовано) — это написать программку, которая найдет мне решение.
Сначала принялся за JavaScript, как не требующий ничего, кроме блокнота и браузера. Когда понял, что медленно получается, перекинул на с++, доработал и эта зараза нашла мне все возможные варианты, в том числе и вожделенные 40 ходов :)
Вероятно, вы видели игрушку
users.cosmostv.by/rmaksim/coding/yours40moves/yours40moves.html
где нужно переставить шарики за 40 ходов.
Так вот первое, что мне пришло в голову (и было реализовано) — это написать программку, которая найдет мне решение.
Сначала принялся за JavaScript, как не требующий ничего, кроме блокнота и браузера. Когда понял, что медленно получается, перекинул на с++, доработал и эта зараза нашла мне все возможные варианты, в том числе и вожделенные 40 ходов :)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Счастливые билеты