Terinspirasi oleh masalah keempat dari BMO2 2009 .

Dengan bilangan bulat positif n sebagai input atau parameter, kembalikan jumlah bilangan bulat positif yang representasi binernya terjadi sebagai blok dalam ekspansi biner dari n .

Misalnya, 13 -> 6 karena 13 dalam biner adalah 1101 dan memiliki substring 1101, 110, 101, 11, 10, 1 . Kami tidak menghitung angka biner yang dimulai dengan nol dan kami tidak menghitung nol itu sendiri.

Uji Kasus

13 -> 6
2008 -> 39
63 -> 6
65 -> 7
850 -> 24
459 -> 23
716 -> 22
425 -> 20
327 -> 16

Anda dapat menerima n sebagai berikut:

• bilangan bulat
• daftar nilai kebenaran / kepalsuan untuk representasi biner
• string untuk representasi biner
• string 10 basis (meskipun saya tidak yakin mengapa ada orang yang melakukan ini)

Buat kode Anda sesingkat mungkin.

Python 3, 54 50 byte

lambda n:sum(bin(i)[2:]in bin(n)for i in range(n))

Terima kasih kepada Rod dan Jonathan Allan karena telah menghemat empat byte.

Jelly , 4 byte

ẆQSḢ

Cobalah online!

Mengambil input sebagai daftar 0s dan1 s.

Cobalah online dengan angka!

Penjelasan:

ẆQSḢ Argument: B = list of bits, e.g. [1, 1, 0, 1]
Ẇ    Get B's non-empty sublists (i.e. [[1], [1], [0], [1], [1, 1], [1, 0], [0, 1], [1, 1, 0], [1, 0, 1], [1, 1, 0, 1]])
 Q   Keep first occurrences (i.e. [[1], [0], [1, 1], [1, 0], [0, 1], [1, 1, 0], [1, 0, 1], [1, 1, 0, 1]])
  S  Reduce by vectorized addition (i.e. [6, 4, 1, 1])
   Ḣ Pop first element (i.e. 6)

Bukti kerjanya:

Program ini mendapat nomor input, N . Hal pertama yang dilakukan produk ini adalah, tentu saja, mengambil substring N ₂ ( N dalam basis 2 ). Ini termasuk duplikat substring dimulai dengan 0 atau 1 .

Setelah itu, kita cukup mengambil substring unik dengan hanya mempertahankan kemunculan pertama dari setiap nilai dalam daftar substring.

Kemudian, program ini merangkum elemen pertama dari daftar bersama-sama, lalu elemen kedua, lalu yang ketiga, keempat, dll. Dan jika salah satu daftar tidak memiliki elemen seperti 0itu diasumsikan. Apa tantangannya ditanyakan secara efektif. Berapa banyak substring unik yang dimulai dengan 1 yang angka ini miliki dalam bentuk binernya? . Karena setiap elemen pertama yang akan dihitung adalah 1, kita bisa menjumlahkan alih-alih memfilter untuk substring yang sesuai.

Sekarang, elemen pertama dari daftar yang dihasilkan dari penjumlahan yang dijelaskan di atas memegang hitungan bit pertama dari substring, jadi kita cukup pop dan akhirnya mengembalikannya.

Oktaf , 62 61 byte

@(n)sum(arrayfun(@(t)any(strfind((g=@dec2bin)(n),g(t))),1:n))

Cobalah online!

Penjelasan

Untuk input n, kode menguji semua angka dari 1untuk nmelihat apakah representasi biner mereka adalah substring dari representasi biner input.

@(n)                                                          % Anonymous function of n
        arrayfun(                                      ,1:n)  % Map over range 1:n
                 @(t)                                         % Anonymous function of t
                         strfind(               ,    )        % Indices of ...
                                                 g(t)         % t as binary string ...
                                 (g=@dec2bin)(n)              % within n as binary string
                     any(                             )       % True if contains nonzero
    sum(                                                    ) % Sum of array

05AB1E , 5 byte

Mengambil input sebagai string biner.
Header mengubah input integer ke biner untuk kemudahan pengujian.

ŒCÙĀO

Cobalah online!

Penjelasan

Π       # push all substrings of input
 C       # convert to base-10 int
  Ù      # remove duplicates
   Ā     # truthify (convert non-zero elements to 1)
    O    # sum

Perl 5 , 36 +1 ( -p) = 37 byte

/.*(.+?)(?{$k{0|$1}++})(?!)/;$_=%k-1

Cobalah online!

Mengambil input sebagai string biner.

PowerShell , 103 92 82 byte

param($s)(($s|%{$i..$s.count|%{-join$s[$i..$_]};$i++}|sort -u)-notmatch'^0').count

Cobalah online!

Mengambil input sebagai larik 1dan 0(truey and falsey di PowerShell). Loop melalui $s(yaitu, berapa banyak elemen dalam array input). Di dalam loop, kami loop dari nomor saat ini (disimpan sebagai $i) hingga $s.count. Setiap loop bagian dalam, kita -joinlarik array menjadi string. Kami kemudian sortdengan -ubendera nique (yang lebih pendek dari selectdengan -ubendera nique dan kami tidak peduli apakah mereka diurutkan atau tidak), ambil yang tidak memulai 0, dan ambil keseluruhan .count. Yang tersisa pada pipa dan output tersirat.

JavaScript (ES6), 55 byte

f=(s,q="0b"+s)=>q&&s.includes((q--).toString(2))+f(s,q)

Mengambil input sebagai string biner.

Berikut ini adalah upaya menyedihkan untuk melakukannya dengan angka dan fungsi rekursif:

f=(n,q=n)=>q&&(g=n=>n?n^q&(h=n=>n&&n|h(n>>1))(q)?g(n>>1):1:0)(n)+f(s,q-1)

Pendekatan lama, 74 byte

s=>(f=s=>+s?new Set([+s,...f(s.slice(1)),...f(s.slice(0,-1))]):[])(s).size

Juga mengambil input sebagai string biner.

Python 2 ,  118  81 byte

Terima kasih kepada @Rod karena telah menghemat 37 byte!

lambda n:len({int(n[i:j+1],2)for i in range(len(n))for j in range(i,len(n))}-{0})

Mengambil input sebagai string biner.

Cobalah online!

Python 2 , 81 byte

Terima kasih kepada @Rod!

lambda n:len({n[i:j+1]for i in range(len(n))for j in range(i,len(n))if'1'==n[i]})

Mengambil input sebagai string biner.

Cobalah online!

Jelly , 5 byte

ẆḄQṠS

Cobalah online!

Mengambil input sebagai daftar 1s dan 0s. Footer di tautan menerapkan fungsi ke masing-masing contoh dalam posting.

Jonathan Allan menunjukkan bahwa ẆḄQTLada alternatif 5 byte yang menggunakan Tatom yang menemukan indeks semua elemen kebenaran.

Penjelasan

Ambil bin (13) = 1101 sebagai contoh. Masukan adalah[1,1,0,1]

ẆḄQṠS
Ẇ       All contiguous sublists -> 1,1,0,1,11,10,01,110,101,1101 (each is represented as a list)
 Ḅ      From binary to decimal. Vectorizes to each element of the above list -> 1,1,0,1,3,2,1,6,5,13
  Q     Unique elements
   Ṡ    Sign. Positive nums -> 1 , 0 -> 0.
    S   Sum

Mengambil ide "benarkan" (masuk dalam kasus ini) dari jawaban 05AB1E

R , 88 77 byte

function(x)sum(!!unique(strtoi(mapply(substring,x,n<-1:nchar(x),list(n)),2)))

Cobalah online!

Mengambil input sebagai string biner.

menggunakan mapply, menghasilkan array dari semua substring dari input. strtoimengonversinya sebagai 2bilangan bulat basis , dan saya mengambil jumlah dari konversi logis ( !!) dari entri dalam hasilnya.

Retina , 37 29 byte

.+
*
+`(_+)\1
$1#
#_
_
wp`_.*

Cobalah online! Saya hanya perlu mencoba wmodifier Retina 1.0 . Sunting: Disimpan 8 byte berkat @MartinEnder. Penjelasan:

.+
*

Konversi dari desimal ke unary.

+`(_+)\1
$1#
#_
_

Konversi dari unary ke binary, gunakan #untuk 0dan_ untuk 1.

wp`_.*

Hasilkan substring yang dimulai dengan 1, maksud saya _,. The wpengubah kemudian cocok dengan semua substring, bukan hanya satu terpanjang di setiap awal _, sedangkan pdeduplicates pengubah pertandingan. Akhirnya karena ini adalah tahap terakhir, hitungan pertandingan dikembalikan secara implisit.

Pyth , 8 byte

l #{vM.:

Coba di sini!

Mengambil input sebagai string biner.

.:menghasilkan semua substring, vMmengevaluasi masing-masing (yaitu, itu mengkonversi masing-masing dari biner), {deduplicate, <space>#filter berdasarkan identitas dan lmendapatkan panjangnya.

Bahasa Wolfram (Mathematica) , 35 byte

Menghitung urutan unik dari representasi biner yang dimulai dengan satu, meskipun saya tidak yakin kode ini bahkan perlu penjelasan.

Union@Subsequences@#~Count~{1,___}&

Cobalah online!

Perl 6 , 47 byte

->\n{+grep {n.base(2).contains(.base: 2)},1..n}

Cobalah online!

Julia 0,6 , 37 byte

~n=sum(contains.([bin(n)],bin.(1:n)))

Cobalah online!

Juliafikasi jawaban Python oleh J843136028 digunakan .untuk aplikasi fungsi elemen-bijaksana dengan penyiaran. ( tautan )

Java, 232 byte

String b=toBin(n);
l.add(b);
for(int i=1;i<b.length();i++){
for(int j=0;j<=b.length()-i;j++){
String t="";
if((""+b.charAt(j)).equals("0"))continue;
for(int k=0;k<i;k++){
t+=""+b.charAt(j+k);
}
if(!l.contains(t))l.add(t);
}
}
return l.size();

Di mana n adalah input, b adalah representasi biner dan l adalah daftar semua substring. Pertama kali memposting di sini, pasti perlu ditingkatkan, dan jangan ragu untuk menunjukkan kesalahan! Diedit sedikit agar mudah dibaca.

Attache , 35 byte

`-&1@`#@Unique@(UnBin=>Subsets@Bin)

Cobalah online!

Setara:

{#Unique[UnBin=>Subsets[Bin[_]]]-1}

Penjelasan

Saya akan menjelaskan versi kedua, karena lebih mudah untuk mengikuti (secara eksplisit):

{#Unique[UnBin=>Subsets[Bin[_]]]-1}
{                                 }   lambda: _ = first argument
                        Bin[_]        convert to binary
                Subsets[      ]       all subsets of input
         UnBin=>                      map UnBin over these subsets
  Unique[                      ]      remove all duplicates
 #                              -1    size - 1 (since subsets is improper)

Ruby 41 36 27 byte

Mengambil string biner sebagai input

Sangat tidak efisien

->n{(?1..n).count{|j|n[j]}}

Sebagian terinspirasi oleh jawaban python 3 ini

Cobalah online!

Java 8, 160 159 158 byte

import java.util.*;b->{Set s=new HashSet();for(int l=b.length(),i=0,j;i<l;i++)for(j=l-i;j>0;s.add(new Long(b.substring(i,i+j--))))s.add(0L);return~-s.size();}

Input sebagai biner-String.
Harus ada cara yang lebih singkat ..>.>

Penjelasan:

Cobalah online.

import java.util.*;          // Required import for Set and HashSet
b->{                         // Method with String as parameter and integer as return-type
  Set s=new HashSet();       //  Create a Set
  for(int l=b.length(),      //  Set `l` to the length of the binary-String
      i=0,j;i<l;i++)         //  Loop from 0 up to `l` (exclusive)
    for(j=l-i;j>0;           //   Inner loop from `l-i` down to `0` (exclusive)
      s.add(new Long(b.substring(i,i+j--))))
                             //    Add every substring converted to number to the Set
      s.add(0L);             //    Add 0 to the Set
  return~-s.size();}         //  Return the amount of items in the Set minus 1 (for the 0)

C ++, 110 byte

#include<set>
std::set<int>s;int f(int n){for(int i=1;i<n;i+=i+1)f(n&i);return n?s.insert(n),f(n/2):s.size();}

Ini adalah fungsi rekursif. Kami menggunakan astd::set untuk menghitung nilai, mengabaikan duplikat. Dua panggilan rekursif menutupi bit dari kiri ( f(n&i)) dan dari kanan ( f(n/2)), akhirnya menghasilkan semua substring sebagai bilangan bulat.

Perhatikan bahwa jika Anda ingin memanggilnya lagi, s harus dihapus di antara panggilan.

Program uji

#include <cstdlib>
#include <iostream>

int main(int, char **argv)
{
    while (*++argv) {
        auto const n = std::atoi(*argv);
        s={};
        std::cout << n << " -> " << f(n) << std::endl;
    }
}

Hasil

./153846 13 2008 63 65 850 459 716 425 327
13 -> 6
2008 -> 39
63 -> 6
65 -> 7
850 -> 24
459 -> 23
716 -> 22
425 -> 20
327 -> 16

J , 34 byte

f=.3 :'<:#~.,(#:i.2^##:y)#.;.1#:y'

Cobalah online!

J , 15 byte

#.\\.#@=@-.&,0:

Input adalah daftar biner. Cobalah online!

#.\\.               Convert every substring to decimal
         -.&,0:     Flatten and remove the 0s.        
     #@=            How many unique elements?

Perl 6 , 34 byte

{+unique ~«(.base(2)~~m:ex/1.*/)}

Menguji

Diperluas:

{
  +                                # turn into Numeric (number of elements)
   unique                          # use only the unique ones
          ~«(                      # turn into strings
             .base(2)              # the input in base 2
                     ~~
                       m:ex/1.*/   # :exhaustive match substrings
                                )
}