Рассмотрим следующую числовую последовательность:
Он перечисляет все двоичные дроби в единичном интервале .
(Чтобы облегчить эту задачу, первый элемент является необязательным: вы можете пропустить его и считать, что последовательность начинается с 1/2.)
задача
Напишите программу (полную программу или функцию), которая ...
Выберите один из следующих вариантов поведения:
- Введите n, выведите n-й элемент последовательности (0-индексированный или 1-индексированный);
- Введите n, выведите первые n элементов последовательности;
- Ничего не вводите, выводите бесконечную последовательность чисел, которую вы можете взять один за другим;
правило
- Ваша программа должна как минимум поддерживать первые 1000 элементов;
- Вы можете выводить десятичные дроби или дроби (встроенные, целочисленные пары, строки), как вам нравится;
- Ввод / вывод в виде двоичных цифр в этом вопросе не допускается;
- Это код-гольф , самые короткие коды выигрывают;
- Стандартные лазейки запрещены.
Testcases
input output
1 1/2 0.5
2 1/4 0.25
3 3/4 0.75
4 1/8 0.125
10 5/16 0.3125
100 73/128 0.5703125
511 511/512 0.998046875
512 1/1024 0.0009765625
Эти примеры основаны на 0-индексированной последовательности с включением 0 в начале. Вам нужно будет настроить вход для соответствия вашему решению.
Подробнее
- OEIS A006257
- Задача Иосифа: . (Ранее M2216)
- 0, 1, 1, 3, 1, 3, 5, 7, 1, 3, 5, 7, 9, 11, 13, 15, 1, 3, 5, ...
- OEIS A062383
- : для п > 0 , п = 2 ⌊ л о г 2 н + 1 ⌋ или п = 2 ⌊ п.
- 1, 2, 4, 4, 8, 8, 8, 8, 16, 16, 16, 16, 16, 16, 16, 16, 32, 32, 32, ...
A006257 (n) / A062383 (n) = (0, 0,1, 0,01, 0,11, 0,001, ...) перечисляет все двоичные дроби в единичном интервале [0, 1). - Фредрик Йоханссон, 14 августа 2006 г.
"1/2" "1/4" "1/8"...
take
n элементов из него позже.int
s, или adouble
в языке / реализации, гдеdouble
используется формат двоичных символов IEEE ? Надеюсь, вы не имеете в виду, нужно ли было анализировать строку ASCII, если мы хотим получить целочисленный ввод? Обычные целочисленные типы являются двоичными в таких языках, как C. Или вы имеете в виду, что ввод / вывод не может быть массивом или строкой целых или ASCII нулей / единиц?Ответы:
Haskell , 25 байт
Попробуйте онлайн!
Вывод десятичных дробей, индексируемых без начального нулевого члена.
Добавляет 0,5 к входу, затем делит пополам до тех пор, пока результаты не станут меньше 2, затем вычитает 1. Использование выражения без точек экономит на 1 байт более
источник
Java 10,
6864 байтаСначала попробуйте код гольф!
Вариант 1: найти n-й элемент (1-индексированный)
-4 байта благодаря @Kevin Cruijssen
This is an anonymous method that finds the n-th term by removing the most significant bit from n, doubling it and adding one, then dividing by the next highest power of 2.
Try it online!
Code walkthrough:
Will edit if it's necessary to print the final value instead of returning it.
источник
{}
цикл после может быть;
вместо; Вы можете удалить пробел послеreturn
;2.0
может быть2.
; И изменяяn>>x!=1;x++
,1<<x
и1<<x+1
кn>>x++!=1;
,1<<x-1
,1<<x
соответственно , также сохраняет байт. Попробуйте онлайн: 64 байта . Приятного пребывания!MathGolf,
54 bytesTry it online!
How it would look like with the operator working correctly
Try it online!
Explanation
I took my inspiration from this question to solve the problem, my "own" solution was around 10-12 bytes I think.
I had intended for the round up to closest power of 2 to return the number itself if it was a number of two, but due to a mistake it rounds to the next power of two (e.g. 4 -> 8 instead of 4 -> 4). This will have to be fixed later, but now it saves me one byte.
источник
]
serves no other purpose than formatting the output, I'd say you don't need to include it in your byte count.Java 10,
8985706968 bytesPort of @Emigma's 05AB1E answer, so outputs decimals indefinitely as well.
-15 bytes thanks to @Arnauld.
Try it online.
Explanation:
источник
Perl 6, 19 bytes
Try it online!
источник
Python 3, 33 bytes
Try it online!
Outputs decimals, one-indexed without the initial zero term.
источник
Java (JDK 10), 30 bytes
Try it online!
Returns the nth item in the sequence.
This answer is originally a succession of golfs of TCFP's Java answer. In the end, the golfs didn't look like the original answer anymore (though the math used is the same) so I decided to post the golfs as a separate answer instead of simply commenting on the TCFP's answer. So if you like this answer, go upvote TCFP's answer as well! ;-)
Intermediate golfs were:
источник
05AB1E,
118 bytesSaved 3 bytes thanks to Kevin Cruijssen.
Try it online!
Explanation
источник
∞
(infinite list starting at 1):∞oεDÅÉs/}˜
[1,2,4,4,8,8,8,8,16,16,...,2**n]
and prepending the correct indexed prime followed by a/
... But that wasn't working so well. Well, but not8-bytes
well. Something like9LoDÅP)ζ
.Jelly, 9 bytes
Try it online!
источник
PowerShell, 40 bytes
Try it online!
Outputs the infinite sequence as decimal values. Given language limitations, will eventually run into precision problems, but easily handles the first 1000 entries.
Starts by setting
$i=2
, then enters afor
loop. Each iteration, we construct a range from1..$i
and pull out the odd values with|?{$_%2}
. Those are fed into their own inner loop, where we divide each to get the decimal|%{$_/$i}
. Those are left on the pipeline and output when the pipeline is flushed after everyfor
iteration. Each iteration we're simply incrementing$i
by$i*=2
to get the next go-round.источник
Haskell,
3532 bytesEdit: -3 bytes thanks to @Delfad0r.
This is an infinite list of integer pairs.
Try it online!
источник
Haskell, 40 bytes
Try it online!
Infinite sequence as pairs of integers (starting from
(1,2)
).Quite a bit longer than @nimi's answer, but the approach is completely different, so I decided to post it anyway.
This solution is based on the following observation.
Consider the infinite sequence{12,14,34,18,38,58,78,116,316,…}
and apply the following steps.
Notice how you get back to the sequence you started with!
The solution exploits this fact (together with Haskell's laziness) to compute the sequence
s
.источник
Python 2 -
6866 bytes-2 bytes thanks to Kevin
Try it Online!
источник
return 2*(n-a)
toreturn(n-a)*2
. And you could save an additional byte by using Python 2 instead of 3, soreturn
can beprint
(with parenthesis).len
andbin
instead oflog
.Python 3,
5351 bytesn
.Try it online!
источник
def f(m=2,n=1):n<m and print(n/m)&f(m,n+2)or f(m+m)
R, 42 bytes
Try it online!
Returns a pairN=2∗(n−2⌊log2(n)⌋)+1 from the Josephus sequence and D=2⌊log2(n)⌋+1 from the other sequence. Happily we are able to re-use the denominator as the two formulas have quite a lot in common!
Denominator,Numerator
. Uses the formulaисточник
Racket,
9291 bytesTry it online!
источник
MATL, 8 bytes
Try it online!
Returns Numerator, then Denominator. Uses the same method as my R answer, although it's a bit more efficient.
Explanation, with input
5
:источник
Shakespeare Programming Language, 426 bytes
Try it online!
Outputs the sequence infinitely as both numbers separated by a space, with each item being separated by a newline.
источник
You be twice the sum of a cat
Python 2, 44 bytes
Try it online!
Function returns a tuple of (numerator, denominator). An input of 0 is not handled (it was optional).
источник
return 2*n-m+1,m
can beprint-~n+n-m,m
to save 2 bytes.Excel
4828 BytesSaved 20 bytes (!) thanks to tsh
=MOD(A1+0.5,2^(INT(LOG(A1,2))))/2^INT(LOG(A1,2))Assumes value in A1, output is in decimal. If you want the output to be in fraction, you can create a custom format for the output cell as "0/###0" and it will show it as fraction.
Explanation: Difficult to explain, since there is a shortcut taken to get to this formula. Basically the numerator is a bit shift left of the input, and the denominator is the next power of 2 higher than the number input.
I originally started with Excel built in functions for BITLSHIFT and BITRSHIFT, but they will shift the entire 48 bits which is not what you want. The functions DEC2BIN (and BIN2DEC) have a limit of -512 to 511 (10 bits) so this wouldn't work. Instead I had to rebuild the number with a modulus of the original number, then times two, then add 1 (since the left digit would always be 1 before a shift).
Examples:
источник
=(A1+0.5)/2^INT(LOG(A1,2))-1
?C++,
977571 bytes-26 bytes thanks to tsh, ceilingcat, Zacharý
Testing code :
источник
if(!i)return 0;
since 0 is not required in the challenge.while
but tryfor
.for(;exp;)
is as same aswhile(exp)
but you can write two more other statement into it. Prefer?:
instead ofif else
, which would be shorter in most cases.(...)
aroundd-n-1
.C (gcc), 63 bytes
No input, prints infinite sequence:
Try it online!
источник
JavaScript (ES6), 44 bytes
Returns then -th term, 1-indexed.
Try it online!
источник
Ruby, 42 bytes
Try it online!
Prints integer pairs infinitely, starting from 1/2.
источник
JavaScript (Node.js), 30 bytes
Try it online! 0-indexed. Started out as a port of my Batch answer but I was able to calculate in multiples of12 which saved several bytes.
источник
Ruby, 31 bytes
Try it online!
источник
><>,
1918 bytesUsing xnor's idea, fixed by Jo King, -1 byte by making better use of the mirrors and another -2 bytes by Jo King because the
!
was superfluous and;
is not required.Try it online!
источник
-0.25
. Fix for the same amount of bytesWolfram Language (Mathematica), 22 bytes
Try it online!
источник
APL (Dyalog Unicode), 15 bytes
Try it online!
Anonymous prefix lambda.
Thanks to Adám for 4 bytes and to Cows quack for 2 bytes.
How:
источник
C# (.NET Core), 69 bytes
Try it online!
Ungolfed:
источник