python 字母順序計數

Problem statement:

問題陳述：

The count-and-say sequence is the sequence of integers with the first five terms as following:

計數序列是具有前五個項的整數序列，如下所示：

1. 1

   1個

2. 11

   11

3. 21

   21

4. 1211

   1211

5. 111221

   111221

1 is read off as "one 1" or 11.

1被讀出為“一個1”或11。

11 is read off as "two 1s" or 21.

11被讀出為“兩個1”或21。

21 is read off as "one 2, then one 1" or 1211.

21被讀出為“一個2，然后一個1”或1211。

That means every integer (repeated continuously) is read off with its count value.

這意味著將讀取每個整數(連續重復)及其計數值。

For a given n, Print the count and say sequence.

對于給定的n ，打印計數并說出順序。

Examples

例子

For n=0
It's a blank string
-------------------------
For n=1
Its "1"
-------------------------
For n=2, we need to evaluate the previous string which is for n=1
For n=1
"1"
So one "1"
Thus For n=2
"11"
-------------------------
Needless to say for n=3
Evaluating n=2 results in two "1"->"21"
So on...

Solution:

解：

Pre-requisite:

先決條件：

to_string function: In C++ we have an in-build function which converts a numerical value to its string representation. Like 1 is converted to "1" (the first 1 is of int datatype, while the second is of string datatype).

to_string函數：在C ++中，我們有一個內置函數，該函數將數字值轉換為其字符串表示形式。 像1轉換為“ 1”(第一個1是int數據類型，而第二個是字符串數據類型)。

prototype of the function is:

該函數的原型是：

    string to_string (int value);

Algorithm:

算法：

1. Check for base cases

   檢查基本情況

2.     if(n==0)
   return "";
   if(n==1)
   return "1";
   
   

3. For rest of the cases, it must start from 1, thus initialize result with string "1". result is our output string which will be printed for each label.

   在其他情況下，它必須從1開始，因此用字符串“ 1”初始化結果 。 結果是將為每個標簽打印的輸出字符串。

4. Print result for level 1. (As level >1 now)

   打印級別1的結果 。(現在級別> 1)

5. Declare a temporary string only to get the current level result. Let the temporary string be temp.

   聲明一個臨時字符串只是為了獲得當前級別的結果。 讓臨時字符串為temp 。

6. For i=1:n //iterate for rest of the rows

   對于i = 1：n //重復其余行

   1. Store the length of result (carrying the result of last processed level actually) string length
   2. 存儲結果的長度(實際攜帶最后處理的水平的結果)字符串的長度
   3. Let the length be len
   4. 讓長度為len
   5. For j=0:lentemp=temp+ to_string(count) + result[j] //count comes first
   6. 對于j = 0：len temp = temp + to_string(count)+ result [j] //首先計數
   7. Current level string is processed in temp, So update result=temp
   8. 當前級別的字符串在temp中處理，因此update result = temp
   9. Print result
   10. 打印結果
   11. Clear temp for further levels
   12. 清除溫度以達到更高的水平

7. End For

   結束于

C++ implementation

C ++實現

#include <bits/stdc++.h>
using namespace std;
void countAndSay(int n) {
//base cases
if(n==0)
return "";
if(n==1)
return "1";
//for rest of the cases, it must start from 1   
//initialize result with string "1"
string result="1";
cout<<result<<endl;
string temp;//temporary string to hold levelwise result
for(int i=1;i<n;i++){ //iterate for n-1 rows
//iterate upto current string length
int len=result.length();
for(int j=0;j<len;j++){
int count=1;//initialize count as 1
//find count for repeated number
while(j+1<len && result[j]==result[j+1] ){
count++;
j++;
}
//convert the count to string and add to 
//temprary result, then add original no
temp+=to_string(count)+result[j];
}
//assign temporary result to original result 
//& print for current level 
result=temp;
cout<<result<<endl;
//clear the temporary result
temp="";
}
}
int main(){
int n;
cout<<"count and Say problem.....\n";
cout<<"enter n, no of rows\n";
cin>>n;
//function to print count and say sequence
coutAndSay(n);
return 0;
}

Output

輸出量

First run:
count and Say problem.....
enter n, no of rows
3
Printing Count and Say sequence...
1
11
21
Second run:
enter n, no of rows
6
Printing Count and Say sequence...
1
11
21
1211
111221
312211
Third run:
count and Say problem.....
enter n, no of rows
10
Printing Count and Say sequence...
1
11
21
1211
111221
312211
13112221
1113213211
31131211131221
13211311123113112211

How the program works?

該程序如何工作？

Let's solve an example for n=3
Base case not matched
Result="1"
Thus it prints "1" and proceeds for rest of two level
Output at level-1
1
--------------------------------------------------------
1st iteration
In the outer for loop
i=1 & i< 3
Length of result=1 (result="1")
Inner loop executes only once, since len=1
Thus count=1
temp =to_string(1) +"1"
="1"+"1" ="11"
result="11"
temp=""
output at level-2
11
So output printed up to now:
1
11
--------------------------------------------------------
2nd iteration
In the outer for loop
i=2& i< 3
Length of result=2 (result="11")
Inner loop executes twice, since len=2
Thus count=2 // "1" repeating twice, no other character
temp =""+to_string(2) +"1" ("" is temp previously updated, cleared basically)
="2"+"1" ="21"
result="21"
temp=""
output at level-3
21
So output printed up to now:
1
11
21
--------------------------------------------------------
3rd iteration
i=3 thus loop ends
Output is printed
Thus count and say sequence for n=3
1
11
21

翻譯自: https://www.includehelp.com/icp/count-and-say-sequence.aspx

python 字母順序計數