В число Каталонский ( OEIS ) представляют собой последовательность натуральных чисел часто появляются в комбинаторике.
N-е каталонское число - это число слов Дика (сбалансированные строки в скобках или скобки, такие как [[][]]
; формально определяется как строка, использующая два символа a и b, так что любая подстрока, начинающаяся с начала, имеет число символов, большее или равное числу из символов b, и вся строка имеет одинаковое количество символов a и b) длиной 2n. N-е каталонское число (для n> = 0) также явно определяется как:
Начиная с n = 0, первые 20 каталонских номеров:
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190...
Вызов
Напишите полную программу или функцию, которая принимает неотрицательное целое число n через STDIN или приемлемую альтернативу и выводит n-е каталонское число. Ваша программа должна работать как минимум для входов 0-19.
I / O
вход
Ваша программа должна получать данные из STDIN, аргументы функций или любые приемлемые альтернативы для этого мета-поста. Вы можете прочитать введенное число как его стандартное десятичное представление, унарное представление или байты.
- Если (и только если) ваш язык не может получить ввод из STDIN или любой приемлемой альтернативы, он может получить ввод из жестко закодированной переменной или подходящего эквивалента в программе.
Выход
Ваша программа должна вывести n-е каталонское число в STDOUT, результат функции или любую из приемлемых альтернатив для этого мета-поста. Вы можете вывести каталонское число в его стандартном десятичном представлении, унарном представлении или байтах.
Вывод должен состоять из оценочного каталонского номера, за которым, возможно, следует одна или несколько строк новой строки. Никакие другие выходные данные не могут быть сгенерированы, кроме постоянного вывода интерпретатора вашего языка, который не может быть подавлен (например, приветствие, цветовые коды ANSI или отступ).
Это не о том, чтобы найти самый короткий язык. Это о поиске самой короткой программы на каждом языке. Поэтому я не приму ответ.
В этой задаче языки, более новые, чем проблема, являются приемлемыми, если они имеют реализацию. Разрешается (и даже поощряется) самостоятельно писать этот переводчик для ранее не реализованного языка. Кроме этого, все стандартные правила код-гольфа должны соблюдаться. Материалы на большинстве языков будут оцениваться в байтах в соответствующей существующей кодировке (обычно UTF-8). Также обратите внимание, что встроенные модули для вычисления n-го каталонского числа допускаются.
Каталог
Фрагмент стека в нижней части этого поста создает каталог из ответов а) в виде списка кратчайшего решения для каждого языка и б) в качестве общей таблицы лидеров.
Чтобы убедиться, что ваш ответ обнаружен, начните его с заголовка, используя следующий шаблон уценки:
## Language Name, N bytes
где N
размер вашего представления. Если вы улучшите свой счет, вы можете сохранить старые результаты в заголовке, вычеркнув их. Например:
## Ruby, <s>104</s> <s>101</s> 96 bytes
Если вы хотите включить в заголовок несколько чисел (например, потому что ваш результат равен сумме двух файлов или вы хотите перечислить штрафы за флаг интерпретатора отдельно), убедитесь, что фактический результат является последним числом в заголовке:
## Perl, 43 + 2 (-p flag) = 45 bytes
Вы также можете сделать имя языка ссылкой, которая будет отображаться во фрагменте кода:
## [><>](http://esolangs.org/wiki/Fish), 121 bytes
<style>body { text-align: left !important} #answer-list { padding: 10px; width: 290px; float: left; } #language-list { padding: 10px; width: 290px; float: left; } table thead { font-weight: bold; } table td { padding: 5px; }</style><script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="language-list"> <h2>Shortest Solution by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr> </thead> <tbody id="languages"> </tbody> </table> </div> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr> </thead> <tbody id="answers"> </tbody> </table> </div> <table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table><script>var QUESTION_ID = 66127; var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe"; var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk"; var OVERRIDE_USER = 12012; var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page; function answersUrl(index) { return "https://api.stackexchange.com/2.2/questions/" + QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER; } function commentUrl(index, answers) { return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER; } function getAnswers() { jQuery.ajax({ url: answersUrl(answer_page++), method: "get", dataType: "jsonp", crossDomain: true, success: function (data) { answers.push.apply(answers, data.items); answers_hash = []; answer_ids = []; data.items.forEach(function(a) { a.comments = []; var id = +a.share_link.match(/\d+/); answer_ids.push(id); answers_hash[id] = a; }); if (!data.has_more) more_answers = false; comment_page = 1; getComments(); } }); } function getComments() { jQuery.ajax({ url: commentUrl(comment_page++, answer_ids), method: "get", dataType: "jsonp", crossDomain: true, success: function (data) { data.items.forEach(function(c) { if (c.owner.user_id === OVERRIDE_USER) answers_hash[c.post_id].comments.push(c); }); if (data.has_more) getComments(); else if (more_answers) getAnswers(); else process(); } }); } getAnswers(); var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/; var OVERRIDE_REG = /^Override\s*header:\s*/i; function getAuthorName(a) { return a.owner.display_name; } function process() { var valid = []; answers.forEach(function(a) { var body = a.body; a.comments.forEach(function(c) { if(OVERRIDE_REG.test(c.body)) body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>'; }); var match = body.match(SCORE_REG); if (match) valid.push({ user: getAuthorName(a), size: +match[2], language: match[1], link: a.share_link, }); else console.log(body); }); valid.sort(function (a, b) { var aB = a.size, bB = b.size; return aB - bB }); var languages = {}; var place = 1; var lastSize = null; var lastPlace = 1; valid.forEach(function (a) { if (a.size != lastSize) lastPlace = place; lastSize = a.size; ++place; var answer = jQuery("#answer-template").html(); answer = answer.replace("{{PLACE}}", lastPlace + ".") .replace("{{NAME}}", a.user) .replace("{{LANGUAGE}}", a.language) .replace("{{SIZE}}", a.size) .replace("{{LINK}}", a.link); answer = jQuery(answer); jQuery("#answers").append(answer); var lang = a.language; lang = jQuery('<a>'+lang+'</a>').text(); languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang.toLowerCase(), user: a.user, size: a.size, link: a.link}; }); var langs = []; for (var lang in languages) if (languages.hasOwnProperty(lang)) langs.push(languages[lang]); langs.sort(function (a, b) { if (a.lang_raw > b.lang_raw) return 1; if (a.lang_raw < b.lang_raw) return -1; return 0; }); for (var i = 0; i < langs.length; ++i) { var language = jQuery("#language-template").html(); var lang = langs[i]; language = language.replace("{{LANGUAGE}}", lang.lang) .replace("{{NAME}}", lang.user) .replace("{{SIZE}}", lang.size) .replace("{{LINK}}", lang.link); language = jQuery(language); jQuery("#languages").append(language); } }</script>
Ответы:
C
7852393433 байтаЕще больше магии C (спасибо xsot):
?:
это расширение GNU .На этот раз, расширив повторяемость ниже (спасибо xnor и Thomas Kwa):
-(n+1)
заменяется на~n
, что эквивалентно дополнению до двух и сохраняет 4 байта.Опять как функция, но на этот раз эксплуатируем следующее повторение:
c(n)
вводит бесконечную рекурсию для негативаn
, хотя это не актуально для этой задачи.Поскольку вызов функции кажется приемлемой альтернативой консольному вводу / выводу:
c(n)
принимаетint
и возвращаетint
.Оригинальная запись:
Вместо непосредственного вычисления определения формула переписывается следующим образом:
Формула предполагает
n >= 2
, но код учитываетn = 0
иn = 1
тоже.В C беспорядок выше,
n
иk
играют ту же роль, что и в формуле, в то время какc
как продукт накапливается. Все вычисления выполняются с использованием плавающей запятойdouble
, что почти всегда является плохой идеей, но в этом случае результаты верны, по крайней мере, до n = 19, так что все в порядке.float
сохранил бы 1 байт, к сожалению, он недостаточно точен.источник
c(n){return!n?:(4+6./~n)*c(n-1);}
?:
! По-видимому, это расширение GNU C, но я думаю, что оно по-прежнему подходит.Желе , 4 байта
Попробуйте онлайн!
Как это работает
источник
c
получить2z
иz
как аргументы?CJam, 12 байт
Попробуйте онлайн.
Помимо ввода 11, вам нужно указать виртуальной машине Java использовать больше памяти. И я бы не советовал идти намного дальше 11. Хотя теоретически это работает для любого N, так как CJam использует целые числа произвольной точности.
объяснение
CJam не имеет встроенных биномиальных коэффициентов, и вычисление их из трех факториалов занимает много байтов ... поэтому нам придется сделать что-то лучше, чем это. :)
источник
ri_2*m!1$m!_*/\)/
) в моей реализации. Единственная хорошая вещь - это намного быстрее. :)Mathematica,
1613 байтВстроенные модули, амириты: /
Не встроенная версия (21 байт):
Биноминальная версия (25 байт):
источник
TI-BASIC, 11 байтов
Как ни странно, nCr имеет более высокий приоритет, чем умножение.
источник
Python 3, 33 байта
Использует повторение
Базовый случай 0 обрабатывается как
0**n or
, который останавливается,1
когдаn==0
и в противном случае вычисляет рекурсивное выражение справа. Побитовый оператор~n==-n-1
сокращает знаменатель и экономит на паренсе.Python 3 используется для его деления поплавка. Python 2 может сделать то же самое с еще одним байтом для записи
6.
.источник
n<1
вместо0**n
?True
к ,n==0
а не1
. Конечно,True == 1
ноTrue is not 1
и это печатает по-разному. Я ожидаю, что это не будет разрешено. Вы знаете, есть ли у нас решение по этому поводу?isinstance(True, int) is True
в конце концов.J, 8 байт
Это монадический поезд; он использует формулу (2x nCr x) / (x + 1). Попробуй это здесь .
источник
pl, 4 байта
Попробуйте онлайн.
объяснение
В pl функции извлекают свои аргументы из стека и возвращают результат обратно в стек. Обычно, когда в стеке недостаточно аргументов, функция просто молча завершается сбоем. Однако, что-то особенное происходит, когда количество аргументов в стеке равно единице функции - входная переменная
_
добавляется в список аргументов:По сути, это псевдокод:
источник
Сесос ,
948668 байт8 байтов путем изменения факториала с версии 1 на версию 2.
18 байтов путем вычисления
n!(n+1)!
за один шаг. Во многом вдохновлен алгоритмом теста Денниса .HexDump:
Попробуйте онлайн!
Использует формулу
a(n) = (2n)! / (n!(n+1)!)
.ассемблер
Brainfuck эквивалент
Этот скрипт Retina используется для генерации эквивалента брейкфука. Обратите внимание, что он принимает только одну цифру в качестве аргумента команды и не проверяет, есть ли команда в комментариях.
источник
Пиф, 8
Попробуйте онлайн или запустите Test Suite
объяснение
источник
Серьезно, 9 байт
Шестнадцатеричный дамп:
Попробуйте онлайн
Объяснение:
источник
2n
строки равнаC(2n,n)
. Таким образом:,;u@τ╣║/
для 8 байтов.║
иM
будет работать.JavaScript (ES6), 24 байта
Основано на ответе Python .
Как это работает
Я думаю, что это самое короткое, что можно получить, но предложения приветствуются!
источник
Юлия, 23 байта
Это анонимная функция, которая принимает целое число и возвращает число с плавающей точкой. Используется основная формула бинома. Чтобы назвать его, дайте ему имя, например
f=n->...
.источник
Matlab,
3525 байтОктава, 23 байта
источник
@(n)
вместо функции, анонимные функции в порядке.n
:@(n)nchoosek(2*n,n++)/n
.../++n
тоже не работает. : /𝔼𝕊𝕄𝕚𝕟, 3 символа / 6 байтов
Try it here (Firefox only).
Встроенные ftw! Так рада, что я внедрила math.js на ранней стадии.
Бонусное решение, 12 символов / 19 байт
Try it here (Firefox only).
Ау! 19-й байт!
Оценивает псевдо-ES6 как:
источник
Haskell, 27 байт
Рекурсивная формула. Должен быть способ сэкономить на паренсе ...
Непосредственно взятие продукта было на 2 байта длиннее:
источник
g(n-1)
=>g$n-1
сохраняет один байт. Изменить: на самом деле это не работает, потому что тогда формула интерпретируется как(...*g) (n-1)
.Дьялог АПЛ, 9 байт
Это монадический поезд; он использует формулу (2x nCr x) / (x + 1). Попробуйте это онлайн здесь .
источник
C
122121119108 байтЯ использовал gcc (GCC) 3.4.4 (специальный cygming, gdc 0.12, используя dmd 0.125) для компиляции в среде windows cygwin. Ввод поступает в командной строке. Это похоже на решение Sherlock9 Python, но циклы объединены в один, чтобы избежать переполнения и получить результат до 20-го каталонского числа (n = 19).
источник
main
определении, чтобы сохранить байт.char**v
чемchar *v[]
. (Пробел перед*
не нужен, а типы эквивалентны.)n
.Javagony , 223 байта
Полностью расширен:
источник
Japt, 16 байт
Даже Mathematica короче.
:-/
Попробуйте онлайн!
Неуправляемый и объяснение
Альтернативная версия, основанная на рекурсивной формуле:
источник
Витси , 13 байт
Это функция в Vitsy . Вы спрашиваете, как сделать это программой, которая делает это? Объединить
N
. с:Попробуйте онлайн!
источник
Млечный Путь 1.5.14 , 14 байт
объяснение
или, альтернативно, гораздо более эффективная версия:
Млечный Путь 1.5.14 , 22 байта
объяснение
использование
источник
Clojure / ClojureScript, 53 байта
Clojure может быть довольно неприятным для игры в гольф. Он очень содержательный, но в то же время очень удобочитаемый, но некоторые отличные черты действительно многословны.
(inc x)
более идиоматичен, чем(+ x 1)
и «кажется» более лаконичным, но на самом деле не сохраняет символы. И написание цепочек операций приятнее(->> x inc (/ 6) (- 4))
, но на самом деле это дольше, чем просто делать это безобразно.источник
Пролог, 42 байта
Использование рекурсии - это почти всегда путь к Прологу.
Код:
Пример:
Попробуйте онлайн здесь
источник
*
символ здесь?Октава, 22 байта
источник
Цейлон, 60 байт
Это работает до C 30 , поскольку целые числа Цейлона имеют 64-битные числа со знаком ( переполнение C 31 , будет рассчитано как -4050872099593203).
Я не знаю, есть ли у Цейлона какие-либо встроенные более высокие математические функции, но тогда импорт правильного пакета, вероятно, займет больше времени, чем просто вычисление этого пешком.
источник
R,
352816 байтИзменить: использовать встроенный пакет чисел.
источник
MATL , 8 байт
Попробуйте онлайн!
объяснение
источник
05AB1E , 6 байтов
Объяснение:
источник
R, 28 байт
Не используя пакет, поэтому немного дольше, чем предыдущий ответ
источник