資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++中統計相鄰字元ASCII值差為1的字串數量
給定一個數字num作為輸入。目標是計算長度為num的可能的字串數量，使得所有相鄰字元的ASCII值之差為1。
如果num為2，則字串將為“ab”、“ba”、“bc”、“cb”，……“yz”、“zy”。
讓我們透過例子來理解
輸入 − num=3
輸出 − 相鄰字元ASCII值差為1的字串數量為 − 98
解釋 − 一些示例字串為：“abc”、“aba”、“cde”……“xyx”、“zyz”、“xyz”。
輸入 − num=2
輸出 − 相鄰字元ASCII值差為1的字串數量為 − 50
解釋 − 一些示例字串為：“ab”、“ba”、“cd”……“xy”、“zy”、“yz”。
下面程式中使用的演算法如下
對於長度 = 2。
以a開頭的字串 = “ab”
以b開頭的字串 = “ba”, “bc”
以c開頭的字串 = “cd”, “cb”...............
對於長度 = n。
以a開頭的字串 = 長度為n-1且以b開頭的字串的數量
以b開頭的字串 = 長度為n-1且以a或c開頭的字串的數量
以c開頭的字串 = 長度為n-1且以b或d開頭的字串的數量
我們將使用動態規劃來解決這個問題。
使用一個數組arr[num+1][27]。arr[i][j]中包含長度為i且以字母序號j開頭的字串的數量。所有arr[1][j]對於字串“a”、“b”……“z”都將為1。
其餘的arr[2 to num+1][0 to 25]，設定arr[i][j]=arr[i-1][j+1] (j=0)。否則設定arr[i][j] = arr[i-1][j-1] + arr[i-1][j+1];
結果將是第num行的計數之和。
輸入整數num
函式difference_strings(int num)接收num並返回相鄰字元ASCII值差為1的字串數量
將初始計數設定為0。
用全0初始化arr[num + 1][27]。
用全1初始化arr[1][0 to 25]。
使用兩個for迴圈遍歷二維陣列arr[][]，從第2行到最後一行，列從0到25，遍歷所有26個字母。
對於j=0，起始字元為'a'。將當前計數設定為arr[i][j] = arr[i - 1][j + 1];
否則設定arr[i][j] = (arr[i - 1][j - 1] + arr[i - 1][j + 1])
現在，在上述迴圈結束後，遍歷最後一行並將arr[num][ 0 to 25]新增到計數中。
返回計數作為結果。
示例
#include <bits/stdc++.h>
using namespace std;
int difference_strings(int num){
long int count = 0;
long int arr[num + 1][27];
memset(arr, 0, sizeof(arr));
for (int i = 0; i <= 25; i++){
arr[1][i] = 1;
}
for (int i = 2; i <= num; i++){
for (int j = 0; j <= 25; j++){
if (j == 0){
arr[i][j] = arr[i - 1][j + 1];
}
else{
arr[i][j] = (arr[i - 1][j - 1] + arr[i - 1][j + 1]);
}
}
}
for (int i = 0; i <= 25; i++){
count = (count + arr[num][i]);
}
return count;
}
int main(){
int num = 2;
cout<<"Count of strings where adjacent characters are of difference one are: "<<difference_strings(num);
return 0;
}輸出
如果我們執行上面的程式碼，它將生成以下輸出：
Count of strings where adjacent characters are of difference one are: 50
853 次瀏覽
