Квадратная плотность числа чисел (SNDD) числа, изобретенного мной, - это отношение числа квадратов чисел, найденных в последовательных цифрах, к длине числа. Например, 169 представляет собой трехзначное число, содержащее 4 квадратных числа - 1, 9, 16, 169 - и, таким образом, имеет плотность четырехзначного числа 4/3 или 1,33. Четырехзначное число 1444 имеет 6 квадратов - 1, 4, 4, 4, 144, 1444 - и, следовательно, соотношение 6/4 или 1,5. Обратите внимание, что в предыдущем примере квадраты можно повторять. Кроме того, 441 не допускается, потому что он не может быть найден последовательно внутри номера 1444.

Ваша задача - написать программу, которая ищет в заданном диапазоне A - B (включительно) число с наибольшей квадратной плотностью числа. Ваша программа должна соответствовать следующим спецификациям:

• Возьмите вход A, B в диапазоне от 1 до 1 000 000 000 (1 миллиард). Пример:sndd 50 1000
• В результате верните число с наибольшим SNDD. В случае ничьей верните наименьшее число.
• 0 не считается квадратом в любой форме, 0, 00, 000 и т. Д. Также не учитываются квадраты, начинающиеся с 0, например 049 или 0049.
• Обратите внимание, что все число не должно быть квадратным числом.

Примеры:

sndd 14000 15000
Output: 14441

sndd 300 500
Output: 441

Бонус: Какое число с наибольшим SNDD между 1 и 1 000 000 000? Можете ли вы доказать, является ли это наибольшим из возможных, или может быть большее в более высоком диапазоне?

Текущие результаты:

1. Рубин: 142
2. Windows PowerShell: 153
3. Скала: 222
4. Python: 245

Теперь, когда ответ был выбран, вот моя (невнятная) справочная реализация в JavaScript: http://jsfiddle.net/ywc25/2/

Ruby 1.9, 142 символа

$><<($*[0]..$*[1]).map{|a|n=0.0;(1..s=a.size).map{|i|n+=a.chars.each_cons(i).count{|x|x[0]>?0&&(r=x.join.to_i**0.5)==r.to_i}};[-n/s,a]}.min[1]

• (139 -> 143): исправлен вывод в случае ничьей.

Отвечая на бонус: лучший результат для чисел <1e9 равен 5/3 = 1,666 ..., сгенерированный 144411449 (и, возможно, другие?).

Но вы можете сделать лучше с большими числами. Как правило, если n имеет оценку x, то вы можете объединить две копии n и получить ту же оценку x. Если вам повезло, и n имеет одну и ту же первую и последнюю цифры, то вы можете отбросить одну из этих цифр в конкатенации и немного улучшить свой счет (один менее чем в два раза больше квадратов и один менее чем в два раза больше цифр) ,

n = 11449441 имеет оценку 1,625 и имеет ту же первую и последнюю цифры. Используя этот факт, мы получаем следующую последовательность баллов:

1.625 for 11449441
1.666 for 114494411449441
1.682 for 1144944114494411449441
1.690 for 11449441144944114494411449441
1.694 for 114494411449441144944114494411449441

который дает бесконечную последовательность чисел, которые строго (хотя и убывающие) лучше, чем предыдущие числа, и все, кроме первых 2, лучше, чем лучший результат для чисел <1e9.

Эта последовательность, возможно, не самая лучшая в целом. Он сходится к конечному баллу (12/7 = 1,714), и могут быть другие числа с лучшими баллами, чем предел.

Изменить : лучшая последовательность, сходится к 1,75

1.600 14441
1.667 144414441
1.692 1444144414441
1.706 14441444144414441
1.714 144414441444144414441

Windows PowerShell, 153 154 155 164 174

$a,$b=$args
@($a..$b|sort{-(0..($l=($s="$_").length)|%{($c=$_)..$l|%{-join$s[$c..$_]}}|?{$_[0]-48-and($x=[math]::sqrt($_))-eq[int]$x}).Count/$l},{$_})[0]

Спасибо Ventero за однобайтовое сокращение, я был слишком глуп, чтобы найти себя.

154-байтовая версия пояснила:

$a,$b=$args   # get the two numbers. We expect only two arguments, so that
              # assignment will neither assign $null nor an array to $b.

@(   # @() here since we might iterate over a single number as well
    $a..$b |  # iterate over the range
        sort {   # sort
            (   # figure out all substrings of the number
                0..($l=($s="$_").length) | %{  # iterate to the length of the
                                               # string – this will run off
                                               # end, but that doesn't matter

                    ($c=$_)..$l | %{       # iterate from the current position
                                           # to the end

                        -join$s[$c..$_]    # grab a range of characters and
                                           # make them into a string again
                    }
                } | ?{                     # filter the list
                    $_[0]-48 -and          # must not begin with 0
                    ($x=[math]::sqrt($_))-eq[int]$x  # and the square root
                                                     # must be an integer
                }

            ).Count `  # we're only interested in the count of square numbers
            / $l       # divided by the length of the number
        },
        {-$_}  # tie-breaker
)[-1]  # select the last element which is the smallest number with the
       # largest SNDD

Python, 245 256

import sys
def t(n,l):return sum(map(lambda x:int(x**0.5+0.5)**2==x,[int(n[i:j+1])for i in range(l)for j in range(i,l)if n[i]!='0']))/float(l)
print max(map(lambda x:(x,t(str(x),len(str(x)))),range(*map(int,sys.argv[1:]))),key=lambda y:y[1])[0]

• 256 → 245: Исправлен код разбора аргументов благодаря подсказке Кейта Рэндалла .

Это могло бы быть намного короче, если бы диапазон считывался stdinв отличие от аргументов командной строки.

Редактировать:

Что касается бонуса, мои эксперименты показывают следующее:

Гипотеза 1 . Для каждого n ∈ the число в ℕ _{≤ n} с наибольшим SNDD должно содержать только цифры 1, 4 и 9.

Гипотеза 2. ∃ п ∈ ℕ ∀ я ℕ ∈ _{≥ п} : SNDD ( п ) ≥ SNDD ( я ).

Эскиз доказательства . Набор квадратов с цифрами 1, 4 и 9, скорее всего, конечен . ∎

Скала, 222

object O extends App{def q(i: Int)={val x=math.sqrt(i).toInt;x*x==i}
println((args(0).toInt to args(1).toInt).maxBy(n=>{val s=n+""
s.tails.flatMap(_.inits).filter(x=>x.size>0&&x(0)!='0'&&q(x.toInt)).size.toFloat/s.size}))}

(Требуется Scala 2.9.)

С учетом вопроса о бонусе: вне диапазона максимально возможный SNDD бесконечен.

По крайней мере, если я правильно прочитал вопрос, квадрат типа 100 (10 * 10) считается.

Если вы считаете число 275625, счет 5/6, так как 25, 625, 5625, 75625 и 275625 все квадратные.

Добавление 2 нулей дает: 27562500, который имеет оценку 10/8. Предел этой последовательности составляет 5/2 = 2,5

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

По общему признанию, это не очень хорошее решение, но оно доказывает, что нет никакого верхнего предела SNDD.

Clojure - 185 символов

Вероятно, можно было бы оптимизировать дальше, но здесь идет:

(fn[A,B]((first(sort(for[r[range]n(r A(inc B))s[(str n)]l[(count s)]][(/(count(filter #(=(int%)(max 1%))(for[b(r(inc l))a(r b)](Math/sqrt(Integer/parseInt(subs s a b))))))(- l))n])))1))

Используется как функция с двумя параметрами:

(crazy-function-as-above 14000 15000)
=> 14441

Желе , 21 байт, языковые проблемы

DµẆ1ị$ÐfḌƲS÷L
rµÇÐṀḢ

Попробуйте онлайн!

объяснение

Вспомогательная функция (рассчитывает плотность ввода цифр):

DµẆ1ị$ÐfḌƲS÷L
Dµ              Default argument: the input's decimal representation
  Ẇ             All substrings of {the decimal representation}
      Ðf        Keep only those where
   1ị$          the first digit is truthy (i.e. not 0)
        Ḍ       Convert from decimal back to an integer
         Ʋ     Check each of those integers to see if it's square
           S    Sum (i.e. add 1 for each square, 0 for each nonsquare)
            ÷L  Divide by the length of {the decimal representation}

Основная программа:

rµÇÐṀḢ
rµ              Range from the first input to the second input
  ÇÐṀ           Find values that maximize the helper function
     Ḣ          Choose the first (i.e. smallest)

Программа, возможно, более интересна без Ḣ- таким образом, она возвращает все числа максимальной плотности, а не только одно - но я добавил ее, чтобы соответствовать спецификации.