資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++程式：構建從輸入(a, b)中以‘a’開頭和結尾的DFA
給定一個由字元‘a’和‘b’組成的DFA字串，該字串應該以字元‘a’開頭和結尾，任務是透過DFA查詢該字串是否以‘a’開頭和結尾。
什麼是DFA（確定性有限自動機）？
在計算理論中，它是理論計算機科學的一個分支，確定性有限自動機是一種有限狀態機，它接受或拒絕符號串。確定性指的是計算執行的唯一性。
為了透過DFA查詢字串，並且該字串應該從輸入(a, b)中以‘a’開頭和結尾。由於沒有記憶體的概念，我們只能儲存當前字元，因此DFA無法儲存提供的字串，否則我們可以輕鬆地檢查給定序列/字串的第一個和最後一個字元。
示例
Input: a b b a Output: yes Explanation: The input string starts and ends with ‘a’ Input: a a a b a b Output: no
我們解決上述問題的方法：
因此，我們將為上述問題建立一個DFA，然後根據我們建立的DFA來解決問題。
dfa.jpg
演算法
Start Step 1-> In main() Call function srand(time(0)) to generate random numbers Declare variable as int max = 1 + rand() % 15 Declare and set int i = 0 While(i < max) Declare char data = 'a' + rand() % 2 Print data Increment i IF data = 'a' IF(i = max) Print "YES" End Loop While (i < max) Set data = 'a' + rand() % 2 Print data Increment i If (data = 'a' AND i = max) Print YES\n End Else IF(i = max) Print NO End End End Else Loop While (i < max) Set data = 'a' + rand() % 2 Print data Increment i End Print NO End End Stop
示例
#include <iostream>
#include <time.h>
using namespace std;
int main() {
// for generating random numbers
srand(time(0));
int max = 1 + rand() % 15;
int i = 0;
while (i < max) {
char data = 'a' + rand() % 2;
cout << data << " ";
i++;
if (data == 'a') {
if (i == max)
cout << "YES\n";
while (i < max) {
data = 'a' + rand() % 2;
cout << data << " ";
i++;
if (data == 'a' && i == max) {
cout << "\nYES\n";
} else if (i == max) {
cout << "\nNO\n";
}
}
} else {
while (i < max) {
data = 'a' + rand() % 2;
cout << data << " ";
i++;
}
cout << "\nNO\n";
}
}
return 0;
}輸出
b b a b a b a b b b b b NO
更新於： 2019年12月23日
901 次瀏覽
廣告