我需要找到所有π5000 萬位數的回文3.141592653589793238462643383279502884197169399375105820974944592307816406286... (goes on and on...)
我已將 的所有數字存盤π在 char 陣列中。現在我需要搜索并統計長度為2到15的'回文'的數量。例如，535、979、33、88、14941等都是有效的結果。
我想要的最終輸出基本上如下所示。
Palindrome length Number of Palindromes of this length
-----------------------------------------------------------------
2 1234 (just an example)
3 1245
4 689
... ...
... ...
... ...
... ...
15 0
到目前為止我的邏輯的偽代碼 - 它可以作業但需要永遠
//store all digits in a char array
char *piArray = (char *)malloc(NUM_PI_DIGITS * sizeof(char));
int count = 0; //count for the number of palindromes
//because we only need to find palindroms that are 2 - 15 digits long
for(int i = 2; i <= 15; i ){
//loop through the piArray and find all the palindromes with i digits long
for(int j = 0; j < size_of_piArray; j ){
//check if the the sub array piArray[j:j i] is parlindrom, if so, add a count
bool isPalindrome = true;
for (int k = 0; k < i / 2; k )
{
if (piArray [j k] != piArray [j i - 1 - k])
{
isPalindrom = false;
break;
}
}
if(isPalindrome){
count ;
}
}
}
我現在面臨的問題是回圈遍歷這么大(15-2)=13倍數的陣列需要很長時間。有沒有更好的方法來做到這一點？
uj5u.com熱心網友回復：
這是改編自Caius Jard提出的方法的 C 版本：
void check_pi_palindromes(int NUM_PI_DIGITS, int max_length, int counts[]) {
// store all digits in a char array
int max_span = max_length / 2;
int start = max_span;
int end = NUM_PI_DIGITS max_span;
char *pi = (char *)malloc(max_span NUM_PI_DIGITS max_span);
// read of generate the digits starting at position `max_span`
[...]
// clear an initial and trailing area to simplify boundary testing
memset(pi, ' ', start);
memset(pi end, ' ', max_span);
// clear the result array
for (int i = 0; i <= max_length; i ) {
count[i] = 0;
}
// loop through the pi array and find all the palindromes
for (int i = start; i < end; i ) {
if (pi[i 1] == pi[i - 1]) { //center of an odd length palindrome
count[3] ;
for (n = 2; n <= max_span && pi[i n] == pi[i - n]; n ) {
count[n * 2 1] ;
}
}
if (pi[i] == pi[i - 1]) { //center of an even length palindrome
count[2] ;
for (n = 1; n <= max_span && pi[i n] == pi[i - n]; n ) {
count[n * 2] ;
}
}
}
}
對于陣列中的每個位置，它會在兩個方向上掃描奇數和偶數長度的回文，具有以下優點：
- 單次通過陣列
- 良好的快取區域性，因為從陣列中讀取的所有內容都在當前位置的小范圍內
- 較少的測驗，因為較大的回文僅作為較小回文的擴展進行測驗。
一個小的作業前綴和后綴用于避免對序列的開頭和結尾進行特殊區分。
uj5u.com熱心網友回復：
我無法為 C 解決它，因為我是 C# 開發人員，但我希望轉換將是微不足道的 - 我已嘗試使其盡可能基本
char[] pi = "3.141592653589793238462643383279502884197169399375105820974944592307816406286".ToCharArray(); //get a small piece as an array of char
int[] lenCounts = new int[16]; //make a new int array with slots 0-15
for(int i = 1; i < pi.Length-1; i ){
if(pi[i 1] == pi[i-1]){ //center of an odd length pal
int n = 2;
while(pi[i n] == pi[i-n] && n <= 7) n ;
lenCounts[((n-1)*2 1)] ;
} else if(pi[i] == pi[i-1]){ //center of an even length pal
int n = 1;
while(pi[i n] == pi[i-1-n] && n <= 7) n ;
lenCounts[n*2] ;
}
}
這演示了“爬取字串尋找回文中心，然后在兩個方向上爬離它以尋找相等的字符”技術。
..唯一我不確定的事情，它已經發生在發布的 Pi 中，如果回文重疊，你想要做什么：
3.14159265358979323846264338327950288419716 93993 75105820974944592307816406286
這包含 939 并與它重疊，3993。上面的演算法會找到兩者，所以如果不允許重疊，那么你可能需要擴展它以處理消除較早的回文，如果它們被后來發現的更長的回文重疊
您可以在https://dotnetfiddle.net/tkQzBq使用 c# 版本- 它也有一些除錯列印行。小提琴被限制為 10 秒的執行時間，所以我不知道你是否能夠計時完整的 50 兆位元組?? - 你可能需要在本地運行這個演算法
編輯：修復了答案中的錯誤，但我還沒有修復它；我確實有while(.. n<lenCounts.Length)ie 允許n達到 15，但這將是一個問題，因為它是雙向的..n應該去 7 以保持在計數陣列的范圍內。我已經通過硬編碼 7 對其進行了修補，但您可能希望使其依賴于陣列長度/2 等
uj5u.com熱心網友回復：
好吧，我認為它不能小于O(len*n)，并且你正在這樣做O(len^2*n)，其中2 <= len <= 15，幾乎相同，因為在這種情況下K系數不會改變O符號，但是如果你想避免這個額外的回圈，你可以檢查這些鏈接，為每個長度添加一個計數器應該不難，因為這些代碼正在計算所有這些鏈接，最大可能長度：
source1，source2，source3。
注意：大多數情況下，當您在尋找演算法或優化時，最好聯系 GeekForGeeks。
編輯：O(n^2)時間復雜度和O(n)
輔助空間的可能方法之一如果您愿意，您可以通過陣列更改 unordered_map，無論如何，這里的鍵將是長度，值將是具有該長度的回文數。
unordered_map<int, int> countPalindromes(string& s) {
unordered_map<int, int> m;
for (int i = 0; i < s.length(); i ) {
// check for odd length palindromes
for (int j = 0; j <= i; j ) {
if (!s[i j])
break;
if (s[i - j] == s[i j]) {
// check for palindromes of length
// greater than 1
if ((i j 1) - (i - j) > 1)
m[(i j 1) - (i - j)] ;
} else
break;
}
// check for even length palindromes
for (int j = 0; j <= i; j ) {
if (!s[i j 1])
break;
if (s[i - j] == s[i j 1]) {
// check for palindromes of length
// greater than 1
if ((i j 2) - (i - j) > 1)
m[(i j 2) - (i - j)] ;
} else
break;
}
}
return m;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/450311.html