Jadual Kandungan
Pernyataan Masalah
Contoh Contoh 2
Penjelasan
Kaedah
Algoritma
Contoh: program C++
Output
Kesimpulan
Rumah pembangunan bahagian belakang C++ Hitung rentetan perduaan panjang N yang merupakan gabungan berulang subrentetan

Hitung rentetan perduaan panjang N yang merupakan gabungan berulang subrentetan

Sep 07, 2023 am 10:13 AM
subrentetan rentetan binari Ulangi penyambungan

Hitung rentetan perduaan panjang N yang merupakan gabungan berulang subrentetan

Tujuan artikel ini adalah untuk melaksanakan program yang mengira bilangan rentetan binari panjang N yang dibentuk oleh penggabungan berulang subrentetan.

Matlamatnya adalah untuk menentukan bilangan rentetan perduaan panjang N yang boleh dibuat dengan menggabungkan berulang kali subrentetan individu bagi teks yang diberikan, dengan N ialah integer positif.

Pernyataan Masalah

Laksanakan atur cara yang mengira bilangan rentetan binari panjang N yang berulang kali menggabungkan subrentetan.

Contoh Contoh 1

Let us take the Input, N = 3
Salin selepas log masuk
Output: 2
Salin selepas log masuk
Terjemahan bahasa Cina bagi

Penjelasan

ialah:

Penjelasan

Disenaraikan di bawah adalah rentetan binari yang boleh dilaksanakan dengan panjang N=3, dengan subrentetan berulang kali digabungkan.

"000":The substring "0" is repeatedly concatenated to form this string.
"111":The substring "1" is repeatedly concatenated to form this string.
Salin selepas log masuk

Jadi apabila kita mengira jumlah bilangan semua rentetan ini, jumlah yang kita dapat ialah 2. Oleh itu, keluarannya ialah 2.

Contoh Contoh 2

Let us take the Input, N = 8
Salin selepas log masuk
Output: 16
Salin selepas log masuk
Terjemahan bahasa Cina bagi

Penjelasan

ialah:

Penjelasan

Disenaraikan di bawah adalah rentetan binari yang boleh dilaksanakan dengan panjang N=8 yang mengandungi penyambungan subrentetan berulang.

“00000000”: The substring "0" is repeatedly concatenated to form this string.
“11111111”: The substring "1" is repeatedly concatenated to form this string.
“01010101”: The substring "01" is repeatedly concatenated to form this string.
“10101010”: The substring "10" is repeatedly concatenated to form this string.
"00110011”: The substring "0011" is repeatedly concatenated to form this string.
"11001100”: The substring "1100" is repeatedly concatenated to form this string.
"11011101”: The substring "1101" is repeatedly concatenated to form this string.
"00100010”: The substring "0010" is repeatedly concatenated to form this string.
"10111011”: The substring "1011" is repeatedly concatenated to form this string.
"01000100”: The substring "0100" is repeatedly concatenated to form this string.
"10001000”: The substring "1000" is repeatedly concatenated to form this string.
"00010001”: The substring "0001" is repeatedly concatenated to form this string.
"11101110”: The substring "1110" is repeatedly concatenated to form this string.
"01110111”: The substring "0111" is repeatedly concatenated to form this string.
"01100110”: The substring "0110" is repeatedly concatenated to form this string.
"10011001”: The substring "1001" is repeatedly concatenated to form this string.
Salin selepas log masuk

Jadi apabila kita menjumlahkan jumlah semua rentetan ini, kita mendapat jumlah 16. Oleh itu, keluarannya ialah 16.

Kaedah

Untuk mengira bilangan rentetan perduaan panjang-N yang dibentuk oleh penyambungan subrentetan berulang, kami menggunakan kaedah berikut.

Satu cara untuk menyelesaikan masalah ini dan mengira bilangan rentetan binari N-panjang dengan menggabungkan subrentetan berulang kali.

Masalah di atas boleh diselesaikan berdasarkan fakta bahawa setiap rentetan yang boleh dilaksanakan mengandungi subrentetan berulang yang digabungkan C kali. Oleh itu, panjang rentetan N yang disediakan perlu dibahagikan dengan C untuk menjana semua rentetan berturut-turut.

Jadi, mula-mula cari semua pembahagi N, dan kemudian bagi setiap pembahagi C yang mungkin, cari jumlah bilangan semua rentetan berpotensi yang boleh dibuat dengan menggabungkan nombor ini boleh ditentukan menggunakan 2C. Untuk menentukan jumlah kiraan bagi setiap panggilan rekursif, gunakan teknik yang sama pada pembahagi C dan tolakkannya daripada 2C. Ini juga akan mengambil kira bilangan rentetan pendua yang terdapat di antara mereka.

Algoritma

Algoritma untuk mengira rentetan binari panjang N dengan penyatuan berulang subrentetan yang diberikan di bawah.

  • Langkah pertama − Mulakan

  • Langkah 2 − Takrifkan fungsi untuk mengira bilangan rentetan panjang N supaya ia adalah gabungan subrentetannya.

  • Langkah 3 - Semak sama ada status telah dikira

  • Langkah 4 - Simpan hasil panggilan rekursif semasa atau nilai kiraan

  • Langkah 5 - Ulangi semua pembahagi

  • Langkah 6 - Kembalikan keputusan yang diperoleh

  • Langkah 7 − Berhenti

Contoh: program C++

Ini ialah pelaksanaan program C bagi algoritma di atas untuk mengira bilangan rentetan binari N-panjang yang dibentuk oleh penyambungan subrentetan berulang.

// C++ program for the above approach
#include<bits/stdc++.h>
using namespace std;

// Storing all the states of recurring recursive 
map<int, int> dp;

// Function for counting the number of strings of length n wherein thatstring is a  concatenation of its substrings
int countTheStrings(int n){

   //the single character cannot be repeated
   if (n == 1)
      return 0;
      
   // Checking whether the state is calculated already or not
   if (dp.find(n) != dp.end())
      return dp[n];
      
      // Storing those value of the result or the count for the present recursive call
   int res = 0;
   
   // Iterate through all of the divisors
   for(int d= 1; d <= sqrt(n); d++){
      if (n % d== 0){
         res += (1 << d) -  countTheStrings(d);
         int div1 = n/d;
         if (div1 != d and d!= 1)
         
            // Non-Rep = Total - Rep
            res += (1 << div1) -  countTheStrings(div1);
      }
   }
   
   // Storing the result of the above calculations
   dp[n] = res; 
   
   // Returning the obtained result
   return res;
}
int main(){
   int n = 8;
   cout<< "Count of 8-length binary strings that are repeated concatenation of a substring: "<< endl;
   cout << countTheStrings(n) << endl;
}
Salin selepas log masuk

Output

Count of 8-length binary strings that are repeated concatenation of a substring −
16
Salin selepas log masuk

Kesimpulan

Begitu juga, kita boleh mengira rentetan binari panjang N, yang merupakan gabungan berulang subrentetan.

Dalam artikel ini, cabaran untuk mendapatkan kiraan rentetan perduaan panjang N yang dibentuk oleh penyatuan subrentetan berulang ditangani.

Kod pengaturcaraan C++ disediakan di sini bersama-sama dengan algoritma untuk mengira rentetan binari N-panjang dengan menggabungkan subrentetan berulang kali.

Atas ialah kandungan terperinci Hitung rentetan perduaan panjang N yang merupakan gabungan berulang subrentetan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn

Alat AI Hot

Undresser.AI Undress

Undresser.AI Undress

Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover

AI Clothes Remover

Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool

Undress AI Tool

Gambar buka pakaian secara percuma

Clothoff.io

Clothoff.io

Penyingkiran pakaian AI

AI Hentai Generator

AI Hentai Generator

Menjana ai hentai secara percuma.

Artikel Panas

R.E.P.O. Kristal tenaga dijelaskan dan apa yang mereka lakukan (kristal kuning)
2 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌
Repo: Cara menghidupkan semula rakan sepasukan
1 bulan yang lalu By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: Cara mendapatkan biji gergasi
4 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌

Alat panas

Notepad++7.3.1

Notepad++7.3.1

Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina

SublimeText3 versi Cina

Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1

Hantar Studio 13.0.1

Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6

Dreamweaver CS6

Alat pembangunan web visual

SublimeText3 versi Mac

SublimeText3 versi Mac

Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Cara menggunakan fungsi LOCATE dalam MySQL untuk mencari kedudukan subrentetan dalam rentetan Cara menggunakan fungsi LOCATE dalam MySQL untuk mencari kedudukan subrentetan dalam rentetan Jul 25, 2023 am 09:45 AM

Cara menggunakan fungsi LOCATE dalam MySQL untuk mencari kedudukan substring dalam rentetan Dalam MySQL, terdapat banyak fungsi yang boleh digunakan untuk memproses rentetan. Antaranya, fungsi LOCATE adalah fungsi yang sangat berguna yang boleh digunakan untuk mencari kedudukan substring dalam rentetan. Sintaks fungsi LOCATE adalah seperti berikut: LOCATE(subrentetan, rentetan,[kedudukan]) dengan subrentetan ialah subrentetan untuk ditemui dan rentetan ialah subrentetan untuk ditemui.

Kira bilangan kejadian subrentetan secara rekursif dalam Java Kira bilangan kejadian subrentetan secara rekursif dalam Java Sep 17, 2023 pm 07:49 PM

Diberi dua rentetan str_1 dan str_2. Matlamatnya adalah untuk mengira bilangan kejadian subrentetan str2 dalam rentetan str1 menggunakan prosedur rekursif. Fungsi rekursif ialah fungsi yang memanggil dirinya dalam definisinya. Jika str1 ialah "Iknowthatyouknowthatiknow" dan str2 ialah "tahu" bilangan kejadian ialah -3 Mari kita fahami melalui contoh. Contohnya, input str1="TPisTPareTPamTP", str2="TP";

Fungsi strtok_r() ialah fungsi dalam bahasa C Fungsinya adalah untuk memisahkan rentetan kepada satu siri subrentetan. Fungsi strtok_r() ialah fungsi dalam bahasa C Fungsinya adalah untuk memisahkan rentetan kepada satu siri subrentetan. Aug 26, 2023 am 09:45 AM

Fungsi ini serupa dengan fungsi strtok(). Satu-satunya perbezaan utama ialah _r, yang dipanggil fungsi reentrant. Fungsi reentrant ialah fungsi yang boleh diganggu semasa pelaksanaan. Fungsi jenis ini boleh digunakan untuk menyambung semula pelaksanaan. Oleh itu, fungsi reentrant adalah thread-safe, yang bermaksud ia boleh diganggu dengan selamat oleh thread tanpa menyebabkan sebarang kerosakan. Fungsi strtok_r() mempunyai parameter tambahan yang dipanggil konteks. Dengan cara ini fungsi boleh dipulihkan di lokasi yang betul. Sintaks fungsi strtok_r() adalah seperti berikut: #include<string.h>char*strtok_r(char*string,constchar*limiter,char**

Urutan tidak bertambah terpanjang dalam rentetan binari Urutan tidak bertambah terpanjang dalam rentetan binari Sep 07, 2023 pm 11:13 PM

Dalam masalah ini, kita perlu mencari urutan tidak bertambah terpanjang bagi rentetan yang diberikan. Tidak bertambah bermakna aksara sama ada sama atau dalam susunan menurun. Memandangkan rentetan binari hanya mengandungi "0" dan "1", rentetan yang terhasil hendaklah sama ada bermula dengan "1" dan berakhir dengan "0", atau bermula dan berakhir dengan "0" atau "1". Untuk menyelesaikan masalah ini, kami akan mengira awalan "1" dan akhiran "0" pada setiap kedudukan rentetan dan mencari jumlah maksimum awalan "1" dan akhiran "0". Pernyataan Masalah - Kami diberi rentetan binari str. Kita perlu mencari urutan tidak bertambah terpanjang daripada rentetan yang diberikan. Contoh Input–str="010100"Output–4 menggambarkan bukan rekursif terpanjang

Ungkapan Biasa PHP: Cara mengekstrak aksara tertentu daripada rentetan ke subrentetan pada penghujungnya Ungkapan Biasa PHP: Cara mengekstrak aksara tertentu daripada rentetan ke subrentetan pada penghujungnya Jun 22, 2023 pm 05:33 PM

Ungkapan biasa ialah alat pemprosesan teks yang berkuasa yang boleh digunakan untuk memadankan rentetan dalam corak tertentu. Dalam PHP, ungkapan biasa biasanya digunakan dalam pemprosesan rentetan, pengesahan borang, carian dan penggantian, dsb. Artikel ini akan memperkenalkan cara menggunakan ungkapan biasa PHP untuk mengekstrak aksara tertentu daripada rentetan ke subrentetan pada penghujungnya. Pertama, mari kita lihat contoh. Katakan kami mempunyai rentetan $str yang mengandungi berbilang URL bermula dengan "http://" dan kami ingin mengekstrak URL ini dan menyimpannya dalam

Dalam PHP, fungsi fungsi pack() adalah untuk menukar data kepada rentetan binari Dalam PHP, fungsi fungsi pack() adalah untuk menukar data kepada rentetan binari Aug 31, 2023 pm 02:05 PM

Fungsi pack() mengemas data ke dalam rentetan binari. Pek sintaks(format,args) Format parameter - format untuk digunakan. Berikut ialah nilai yang mungkin - a - rentetan berlapik NUL A - rentetan empuk ruang h - rentetan perenambelasan, nibble rendah dahulu H - rentetan perenambelasan, nibble tinggi dahulu c - char C yang ditandatangani - char s yang tidak ditandatangani - ditandatangani pendek (sentiasa 16 bit , pesanan bait mesin) S - pendek tidak ditandatangani (sentiasa 16 bit, susunan bait mesin) n - pendek tidak ditandatangani (sentiasa 16 bit, susunan bait endian besar) v - pendek tidak ditandatangani (sentiasa 16 bit, susunan bait endian kecil) i - integer bertanda (bergantung pada saiz mesin dan susunan bait) I - Tiada integer yang ditandatangani (bergantung pada

Ditulis dalam C++, cari bilangan pilih atur unik rentetan binari bermula dengan 1 Ditulis dalam C++, cari bilangan pilih atur unik rentetan binari bermula dengan 1 Sep 05, 2023 am 09:01 AM

Dalam masalah yang diberikan, kita diberi rentetan yang terdiri daripada 0 dan 1 kita perlu mencari jumlah bilangan semua pilih atur bermula dengan 1. Oleh kerana jawapannya mungkin jumlah yang besar, kami mengambilnya modulo 1000000007 dan mengeluarkannya. Input:str="10101001001"Output:210Input:str="101110011"Output:56 Kami akan menyelesaikan masalah ini dengan menggunakan beberapa matematik gabungan dan menyediakan beberapa formula. Kaedah Penyelesaian Dalam kaedah ini kita akan mengira bilangan 0 dan 1. Sekarang andaikan n ialah nombor 1 yang muncul dalam rentetan kami dan m ialah bilangan 0 yang muncul dalam rentetan kami

Pertanyaan subrentetan palindromik dalam C++ Pertanyaan subrentetan palindromik dalam C++ Sep 22, 2023 am 09:05 AM

Dalam tutorial ini, kita perlu menyelesaikan pertanyaan subrentetan palindrom untuk rentetan tertentu. Menyelesaikan pertanyaan subrentetan palindrom adalah lebih kompleks daripada menyelesaikan pertanyaan biasa dalam C++. Ia memerlukan kod dan logik yang lebih kompleks. Dalam tutorial ini, kami telah menyediakan pertanyaan string str dan Q substring [L...R], setiap satunya mempunyai dua nilai L dan R. Matlamat kami adalah untuk menulis atur cara yang menyelesaikan pertanyaan untuk menentukan sama ada subrentetan[L...R] ialah palindrom. Kita perlu menentukan sama ada subrentetan yang terbentuk dalam julat L hingga R adalah palindrom untuk menyelesaikan setiap pertanyaan. Contohnya-Mari masukkan"abbbabaaaba"asourinputstring.Thequer

See all articles