Średnie bity: średnie wyzwanie

30

Biorąc pod uwagę liczbę całkowitą N> = 1, wypisz średnią liczbę bitów w liczbie całkowitej od 0 do N - 1

Specyfikacja

  • Dane wyjściowe można obliczyć jako sumę liczby bitów w reprezentacji binarnej każdej liczby całkowitej od 0 do N-1, podzieloną przez N.
  • Binarna reprezentacja liczby całkowitej nie ma w tym kontekście zer wiodących, z wyjątkiem zera, który jest reprezentowany jako 0 w postaci binarnej.
  • Wynik powinien być dokładny co najmniej 7 cyfr znaczących.

Przykład

N = 6

0: 0   : 1 bit
1: 1   : 1 bit
2: 10  : 2 bits
3: 11  : 2 bits
4: 100 : 3 bits
5: 101 : 3 bits

Średnia liczba bitów = (1 + 1 + 2 + 2 + 3 + 3) / 6 = 2

Przypadki testowe

Wejście => wyjście

1 => 1
2 => 1
3 => 1.3333333
4 => 1.5
5 => 1.8
6 => 2
7 => 2.1428571

Fragment tabeli wyników

( stąd )

Pokaż fragment kodu

Zauważ, że suma (przed podzieleniem w celu znalezienia średniej) jest sekwencją w OEIS .

code-golf  math  binary  bitwise  statistics 
— trichopaks
źródło
6
Ładne imię, bardzo punny .
— Rɪᴋᴇʀ
3
Dla każdego, kto nie wie, chętniej głosuję za rozwiązaniem z wyjaśnieniem
— trichoplax
4
Za mało kalamburów, potrzebujesz trochę więcej, aby to było idealne.
— clismique
1
Zakładam, że przez „każdą liczbę” rozumiesz „każdą liczbę całkowitą ”?
— Cyoce
@Cyoce tak, dziękuję za zwrócenie na to uwagi - edytowałem je w celu wyjaśnienia.
— trichoplax

Odpowiedzi:

13

Pyth, 6 bajtów

.Oml.B

Wypróbuj online tutaj .

.Oml.BdUQ              Filling in implict vars

.O                     Average of list
 m   UQ                Map over [0..input)
  l                    Length of
   .B                  Binary string representation of int
    d                  Lambda var
— Maltysen
źródło
Wspólne pierwsze miejsce, ale nie pojawiłeś się na tablicy wyników - wprowadziłem niewielką zmianę w nagłówku, aby to naprawić.
— trichoplax
9

Galaretka, 6 bajtów

R’BFL÷

Wypróbuj online!

R’BFL÷  Main monadic chain. Argument: n

R       yield [1, 2, ..., n]
 ’      decrement; yield [0, 1, ..., n-1]
  B     convert to binary; yield [[0], [1], [1,0], [1,1], ...]
   F    flatten list; yield [0, 1, 1, 0, 1, 1, ...]
    L   length of list
     ÷  divide [by n]
— Leaky Nun
źródło
7

Oktawa, 29 bajtów

@(n)1+sum(fix(log2(1:n-1)))/n

Wyjaśnienie

              log2(1:n-1)       % log2 of numbers in range [1..n-1]
                                % why no 0? because log2(0) = -Inf  :/
          fix(           )      % floor (more or less, for positive numbers)
      sum(                )     % sum... wait, didn't we miss a +1 somewhere?
                                % and what about that missing 0?
                           /n   % divide by n for the mean
    1+                          % and add (1/n) for each of the n bit lengths 
                                % (including 0!)

Próbka uruchomiona na ideone .

— zlewka
źródło
6

Python 3, 43 bajty

def f(n):x=len(bin(n))-2;return(2-2**x)/n+x

Wykorzystuje formułę na stronie OEIS . Zaskakujące jest, że nazwana funkcja jest tutaj nieco tańsza ze względu na przypisanie do x.

Alternatywne podejście dla 46 bajtów:

lambda n:-~sum(map(int.bit_length,range(n)))/n

Niestety, -~ponieważ (0).bit_length()jest to konieczne 0, ale nawet wtedy byłby to bajt za długi.

— Sp3000
źródło
6

Julia, 27 bajtów

n->endof(prod(bin,0:n-1))/n

Wypróbuj online!

Jak to działa

Ponieważ *w Julii jest konkatenacja ciągów, prodmoże być używana do konkatenacji tablicy ciągów. Opcjonalnie przyjmuje funkcję jako pierwszy argument, który odwzorowuje na drugi przed pobraniem rzeczywistego „produktu”, podobnie prod(bin,0:n-1)jak ciąg binarnej reprezentacji wszystkich liczb całkowitych w żądanym zakresie. Biorąc długość endofzi dzieląc przez n daje średnią.

— Dennis
źródło
5

Julia, 28 bajtów

n->mean(ceil(log2([2;2:n])))

Ponieważ binnie mapuje automatycznie tablic, używamy ceil(log2(n))do uzyskania liczby bitów n-1. Działa to dobrze, ponieważ a:bnotacja Julii obejmuje oba końce, podobnie 2:njak zakres od 2 do n, ale tak naprawdę obliczamy liczbę bitów dla liczb z tego zakresu 1:n-1. Niestety musimy jednak zastosować dodatkowe, 2aby uwzględnić 0.

Wypróbuj online!

— Sp3000
źródło
5

MATL, 9 bajtów

q:ZlksG/Q

Wypróbuj online!

Zmodyfikowana wersja ze wszystkimi przypadkami testowymi

Wyjaśnienie

    % Implicitly grab input (N)
q:  % Create array from 1:N-1
Zl  % Compute log2 for each element of the array
k   % Round down to the nearest integer
s   % Sum all values in the array
G   % Explicitly grab input again
/   % Divide by the input
Q   % Add 1 to account for 0 in [0, ... N - 1]
    % Implicitly display the result
— Suever
źródło
Kłapnięcie!! (wypełniacz)
— David
@David W rzeczywistości twój miał rację. Powielanie danych wejściowych na początku nie działa dla innych wartości ... potrzebujesz G/Qna końcu.
— zlewka
5

MATL, 9 bajtów

:qBYszQG/

Wypróbuj online!

Wyjaśnienie

:qBYszQG/
:               % take vector [1..n]
 q              % decrement by 1 to get [0..n-1]
  B             % convert from decimal to binary
   Ys           % cumulative sum (fills in 0's after first 1)
     z          % number of nonzero elements
      Q         % increment by 1 to account for zero
       G        % paste original input (n)
        /       % divide for the mean
— zlewka
źródło
5

Galaretka, 8 bajtów

Nie krótszy, ale interesujący algorytm i moje pierwsze zgłoszenie galaretki:

Rl2Ċ»1S÷

R         1 to n
 l2       log2
   Ċ      ceiling
    »1    max of 1 and...
      S   sum
       ÷  divided by n
— Adám
źródło
4

Galaretka, 10 bajtów

BL©2*2_÷+®

Z sugestii Sp3000.

Wypróbuj tutaj.

Galaretka, 11 bajtów

æḟ2’Ḥ÷_BL$N

Niezbyt krótki, ale potrzebuję kilku wskazówek.

Wypróbuj tutaj.

Przy użyciu tej samej formuły, co w odpowiedzi Sp3000 . (Nie jest bardzo trudno zdobyć go sam, różnicując postęp geometryczny).

— jimmy23013
źródło
Spójrz na moją odpowiedź galaretki w celach informacyjnych.
— Leaky Nun
@LeakyNun Wykorzystuje inne podejście, które nie wydaje mi się, że byłoby krótsze niż twoje. Ale _BL$Nwydawało się dość długie ...
— jimmy23013
Zasadniczo twój kod to „od podłogi do najbliższej potęgi 2, minus 1, podwójne, podziel przez dane wejściowe, minus binarna długość danych wejściowych, ujemne”?
— Leaky Nun
@LeakyNun Tak ..
— jimmy23013
3
Tylko nieznacznie lepiej:BL©2*2_÷+®
— Sp3000,
4

Java, 135 95 90 bajtów

float a(int n){int i=0,t=0;for(;i<n;)t+=Integer.toString(i++,2).length();return t/(n+0f);}
— Shaun Wild
źródło
Myślę, że możesz pozbyć się interfejsu i po prostu utworzyć funkcję lub lambda. Możesz także zwrócić wartość zamiast drukować ją na standardowe wyjście
— Frozn
Okej, wdrożę te zasady.
— Shaun Wild,
Myślę, że należy na to pozwolić. Ponieważ PO nic nie określił myślę standardowe zasady I / O zastosowania.
— Frozn
Tak, funkcja jest w porządku - nie potrzebujesz kompletnego programu. Pamiętaj, że tabela liderów podnosi wynik w pierwszej linii, więc twój wynik obecnie pokazuje się jako 135 zamiast 95.
— trichoplax
@trichoplax Nadal ostatnie miejsce. Osobiście obwiniam Javę ...
— Shaun Wild
3

Python 3, 46 bajtów

lambda x:sum(len(bin(i))-2for i in range(x))/x

Nazwij to jak

f = lambda x: sum(len(bin(i))-2for i in range(x))/x
print(f(6))
# 2.0

Musiałem cofnąć wersję mapy, ponieważ nie udało się wprowadzić 5

— Keatinge
źródło
3

05AB1E, 9 7 bajtów

Kod:

L<bJg¹/

Wyjaśnienie:

L<         # range from 0..input-1
  b        # convert numbers to binary
   J       # join list of binary numbers into a string
    g      # get length of string (number of bits)
     ¹/    # divide by input

Wypróbuj online

Edycja: zapisane 2 bajty dzięki @Adnan

— Emigna
źródło
@Adnan: Dzięki! Zapomniałem o J.
— Emigna
3

C #, 87 bajtów

double f(int n){return Enumerable.Range(0,n).Average(i=>Convert.ToString(i,2).Length);}

Napisałem odpowiedź w języku C #, ponieważ jej nie widziałem. To mój pierwszy post na jednym z nich, więc daj mi znać, jeśli zrobię coś źle.

— raive
źródło
Witamy w Programowaniu zagadek i Code Golf. To świetna pierwsza odpowiedź +1. Czy możesz zmienić doublena, floataby zapisać jeden bajt, czy potrzebujesz precyzji?
— wizzwizz4
2
@ wizzwizz4 Thanks! Miałem tę samą myśl, ale średnia () zwraca wartość podwójną. Jeśli zmienię typ zwracany na zmiennoprzecinkowy, muszę jawnie rzucić podwójny i uzyskać na nim 7 bajtów.
— raive
2

JavaScript (ES7), 38 32 bajtów

n=>(l=-~Math.log2(n))-(2**l-2)/n

Korzystanie z formuły @ sp3000 (poprzednia wersja była rozwiązaniem rekurencyjnym). Wersja ES6 dla 34 bajtów:

n=>(l=-~Math.log2(n))-((1<<l)-2)/n

Wyjaśnienie wzoru: Rozważ przypadek N = 55. Jeśli piszemy liczby binarne (pionowo, aby zaoszczędzić miejsce), otrzymujemy:

                                11111111111111111111111
                111111111111111100000000000000001111111
        11111111000000001111111100000000111111110000000
    111100001111000011110000111100001111000011110000111
  11001100110011001100110011001100110011001100110011001
0101010101010101010101010101010101010101010101010101010

Rozmiar tego prostokąta wynosi nl, więc średnia wynosi tylko l, ale musimy wykluczyć puste miejsca. Każdy rząd pustych miejsc jest dwa razy dłuższy niż poprzedni, więc suma wynosi 2 + 4 + 8 + 16 + 32 = 64 - 2 = 2 l - 2.

— Neil
źródło
2

J, 21 17 15 bajtów

Od 17 bajtów do 15 bajtów dzięki @Dennis.

+/@:%~#@#:"0@i.

Czy ktoś może mi pomóc w golfa? ...

Wersja bez golfa

range        =: i.
length       =: #
binary       =: #:
sum          =: +/
divide       =: %
itself       =: ~
of           =: @
ofall        =: @:
binarylength =: length of binary "0
average      =: sum ofall divide itself
f            =: average binarylength of range
— Leaky Nun
źródło
Próbowałem alternatywnego podejścia, przez stringifying listę liczb binarnych, a wyszedł z 25 bajtów: %~>:@#@([:":10#.[:#:i.)-]. Twoje rozwiązanie wygląda raczej optymalnie.
— Conor O'Brien,
2

Perl 6 ,  34  32 bajty

{$_ R/[+] map *.base(2).chars,^$_}

{$_ R/[+] map {(.msb||0)+1},^$_}

Wyjaśnienie:

{ 
  $_  # the input
  R/  # divides ( ｢$a R/ $b｣ is the same as ｢$b / $a｣ )
  [+] # the sum of:
  map
    {
      (
       .msb # the most significant digit (0 based)
       || 0 # which returns Nil for ｢0.msb｣ so use 0 instead
            # should be ｢(.msb//0)｣ but the highlighting gets it wrong
            # it still works because it has the same end result 
      ) 
      + 1   # make it 1 based
    },
    ^$_ # ｢0 ..^ $_｣ all the numbers up to the input, excluding the input
}

Test:

use v6.c;

# give it a name
my &mean-bits = {$_ R/[+] map {(.msb||0)+1},^$_}

for 1..7 {
  say .&mean-bits
}

say '';

say mean-bits(7).perl;
say mean-bits(7).base-repeating(10);
1
1
1.333333
1.5
1.8
2
2.142857

<15/7>
(2. 142857)
— Brad Gilbert b2gills
źródło
2

Dyalog APL , 14 bajtów

(+/1⌈(⌈2⍟⍳))÷⊢

range ← ⍳
log   ← ⍟
log2  ← 2 log range
ceil  ← ⌈
bits  ← ceil log2
max   ← ⌈
fix0  ← 1 max bits
sum   ← +/
total ← sum fix0
self  ← ⊢
div   ← ÷
mean  ← sum div self
— Adám
źródło
2

Clojure, 71 64 63 bajtów

Wygląda na to, że stosunki są prawidłowe w zależności od tego, które formaty liczb są dopuszczalne w danych wyjściowych?

(fn[n](/(inc(apply +(map #(.bitLength(bigint %))(range n))))n))

  • n = 1 => 1
  • n = 7 => 15/7

bez golfa (i nieco przepisany dla ułatwienia wyjaśnienia)

(fn [n]
 (->
  (->>
   (range n)                      ;;Get numbers from 0 to N
   (map #(.bitLength (bigint %))) ;;Cast numbers to BigInt so bitLength can be used
   (apply +)                      ;;Sum the results of the mapping
   (inc))                         ;;Increment by 1 since bitLength of 0 is 0
  (/ n)))                         ;;Divide the sum by N

stara odpowiedź, która była używana (liczba zmiennoprzecinkowa):

(fn[n](float(/(inc(apply +(map #(..(bigint %)bitLength)(range n))))n)))

wyjście jest jak:

  • n = 1 => 1,0
  • n = 7 => 2,142857
— znak
źródło
Pytanie, czy ułamki czy proporcje są dopuszczalne, nie było wcześniej podnoszone. W przypadku tego wyzwania zaakceptuję osiągnięty konsensus co do domyślnej wartości .
— trichoplax
1

Minkolang 0,15 , 23 bajty

n$z1z[i1+2l$M$Y+]kz$:N.

Wypróbuj tutaj!

Wyjaśnienie

n$z                       Take number from input and store it in register (n)
   1                      Push 1 onto the stack
    z[                    For loop that repeats n times
      i1+                 Loop counter + 1
         2l$M             log_2
             $Y           Ceiling
               +          Add top two elements of stack
                ]         Close for loop
                 z$:      Float divide by n
                    N.    Output as number and stop.

Dość prosta implementacja.

— El'endia Starman
źródło
1

JavaScript ES5, 55 bajtów

n=>eval(`for(o=0,p=n;n--;o+=n.toString(2).length/p);o`)

Wyjaśnienie

n =>   // anonymous function w/ arg `n`
  for( // loop
      o=0,  // initalize bit counter to zero
      p=n   // copy the input
    ;n-- // will decrease input every iteration, will decrease until it's zero
    ;o+=    // add to the bitcounter
        n.toString(2)  // the binary representation of the current itearations's
                     .length // length
        /p   // divided by input copy (to avergage)
   );o       // return o variable
— Downgoat
źródło
1

Hoon , 71 bajtów

|=
r/@
(^div (sun (roll (turn (gulf 0 (dec r)) xeb) add)) (sun r)):.^rq

... Jestem prawie pewien, że tak naprawdę po raz pierwszy użyłem rdzeni zmiennoprzecinkowych Hoon. W rzeczywistości jest to implementacja napisana w języku Hoon, która wypływa na SoftFloat, ponieważ jedynymi typami danych w Hoon są atomy i komórki.

Utworzyć funkcję, która pobiera atomu r. Utwórz listę z [0 .. (r - 1)], zamapuj listę na liście, przyjmując logarytm binarny liczby, a następnie złóż tę listę za pomocą ++add. Konwersja zarówno produkcję zagięcia i rdo @rq(quad precyzji liczb zmiennoprzecinkowych) z ++sun:rq, a następnie dzieli jeden po drugim.

Najdziwniejsze w tym fragmencie jest :.^rqkoniec. a:bin Hoon oznacza „oceń a w kontekście b”. ++rqjest rdzeniem zawierającym całą implementację poczwórnej precyzji, jak biblioteka. Więc bieganie (sun 5):rqto to samo, co robienie (sun:rq 5).

Na szczęście rdzenie w Hoon są jak gniazdujące lalki; gdy oceniasz ramię, ++rqaby uzyskać rdzeń, dodaje do niego cały stdlib, dzięki czemu możesz dalej toczyć się, obracać, przepełniać i wszystkie te fajne rzeczy, zamiast utknąć tylko z ramionami zdefiniowanymi w ++rq. Niestety, rq zmienia definicję ++addna dodawanie zmiennoprzecinkowe, a także nie ma rw swoim kontekście. .(cały aktualny kontekst) tak.

Podczas oceny wyrażenia w kontekście kompilator szuka najpierw głębokości kończyny. W naszym przypadku a:[. rq]wyglądałoby to w całym bieżącym kontekście aprzed przejściem do zaglądania rq. Sprawdzimy więc addfunkcję, która działa na atomy zamiast liczb zmiennoprzecinkowych ... ale tak też będzie div. Hoon ma również funkcję, w której użycie ^nameignoruje pierwsze znalezione odniesienie i szuka drugiego.

Stamtąd używa po prostu cukru syntaktycznego a^bbycia równym do [a b]oceny naszego fragmentu zarówno w naszym obecnym kontekście, jak i bibliotece float o poczwórnej precyzji, ignorując podział atomowy na korzyść ++div:rq.

> %.  7
  |=
  r/@
  (^div (sun (roll (turn (gulf 0 (dec r)) xeb) add)) (sun r)):.^rq
.~~~2.1428571428571428571428571428571428
— RenderSettings
źródło
1

W rzeczywistości 7 bajtów:

;r♂├Σl/

Wypróbuj online!

Wyjaśnienie:

;r♂├Σl/
;        duplicate input
 r       push range(0, n) ([0, n-1])
  ♂├     map binary representation
    Σ    sum (concatenate strings)
     l/  divide length of string (total # of bits) by n

Gdyby nie błąd, który właśnie odkryłem, to rozwiązanie działałoby dla 6 bajtów:

r♂├♂læ

æ to wbudowane polecenie średnie.

— Mego
źródło
Czy to nie 10 bajtów? Sprawdziłem na bytesizematters.com.
— m654
1
@ m654 Właściwie nie używa UTF-8, używa CP437 (lub czegoś takiego).
— Alex A.,
@AlexA. Nie wiedziałem o tym.
— m654
1
@ m654 Bytesizematters używa całkowicie skompilowanego kodowania, które nie istnieje (i nie może ) w praktyce. W przypadku UTF-8 użyj mothereff.in/byte-counter .
— Dennis
@Dennis Dzięki za informację, będę o tym pamiętać.
— m654
1

PowerShell v2 +, 64 bajty

param($n)0..($n-1)|%{$o+=[convert]::ToString($_,2).Length};$o/$n

Bardzo prosta implementacja specyfikacji. Pętle od 0do $n-1z |%{...}. Każdej iteracji podajemy [convert]nasz numer wejściowy $_do podstawy ciągu znaków 2i bierzemy go length. Gromadzimy to w $o. Po pętlach po prostu dzielimy $o/$n, pozostawiając to w potoku, a dane wyjściowe są niejawne.

Tak długo, jak to jest, jest tak naprawdę krótszy niż formuła, której używają Sp i inni, [math]::Ceiling()i [math]::Log()są absurdalnie trudne. Podstawowa konwersja w PowerShell jest pechowa.

— AdmBorkBork
źródło
1

Perl 5.10, 54 bajty

for(1..<>){$u+=length sprintf"%b",$_;$n++}$u/=$n;say$u

Prawie proste. sprintf"%b"to fajny sposób na wyprowadzenie liczby binarnej w Perlu bez użycia dodatkowych bibliotek.

Wypróbuj online!

— Paul Picard
źródło
1

CJam, 13 12 11 bajtów

Jeden bajt zapisany dzięki @ Sp3000, a drugi dzięki @ jimmy23013

rd_,2fbs,\/

Wypróbuj online!

Wyjaśnienie

Bezpośredni. Stosuje definicję.

rd      e# read input and convert to double 
_       e# duplicate 
,       e# range from 0 to input minus 1
2fb     e# convert each element of the array to binary 
s       e# convert to string. This flattens the array
,       e# length of array 
\       e# swap 
/       e# divide
— Luis Mendo
źródło
1

Jolf, 10 bajtów

/uΜr0xdlBH

Wypróbuj tutaj!

Wyjaśnienie

/uΜr0xdlBH
  Μr0x      map range 0..x
      dlBH  over lengths of binary elements
/u          divide sum of this
            by implicit input (x)
— Conor O'Brien
źródło
1

Szybki, 72 bajty

func f(n:Double)->Double{return n<1 ?1:f(n-1)+1+floor(log2(n))}
f(N-1)/N
— John McDowall
źródło
2
Nie musisz wywoływać funkcji, pozostawienie jej jako zdefiniowanej funkcji jest w porządku. Niezły pierwszy post.
— Rɪᴋᴇʀ
1

J, 15 bajtów

%~[:+/#@#:"0@i.

Jest to czasownik monadyczny, używany w następujący sposób:

   f =: %~[:+/#@#:"0@i.
   f 7
2.14286

Wypróbuj tutaj!

Wyjaśnienie

Zaimplementowałem specyfikację wyzwania dosłownie. Istnieją inne podejścia, ale wszystkie okazały się dłuższe.

%~[:+/#@#:"0@i.  Input is y
             i.  Range from 0 to y-1.
          "0@    For each number in this range:
      #@           Compute the length of
        #:         its base-2 representation.
  [:+/           Take the sum of the lengths, and
%~               divide by y.
— Zgarb
źródło
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.