在百度知道上看到一個排列組合的一個提問,一想還是比較容易的主要採用取餘的方法. 這裡用C寫了一段代碼測試了一下.代碼比較水,主要看後面的數學分析. 想想還是高中生 的時候比較厲害,啥都會,啥都算的快. 現在打游戲都力不從心了. 同學們四年游戲專業一定要好好學.不留遺憾.
前言
今天看見一道百度知道上提問,是這樣的.
仔細算了一下, 花了30min.才整齣來了,估計現在回去參加高考,數學及格都懸.有時候想做這樣的題有什麼用,
學這些東西有什麼意義,在這種方面浪費時間有什麼值得的.
後來想出來,
開心就好!
想太多,考慮太多心累.我們開心就好.
正文
第一部分 從代碼說開來
採用的主要思路是窮舉法,窮舉完之後,再判斷. 思考了一下,主要用 char str[5]; 保存這個這個串. 採用下麵函數檢測這個串
是否是想要的串
#inclue <stdbool.h> // 串檢測函數 bool isaa(char str[], int len) { int i = 0; while(++i < len) if (str[i] == 'a' && str[i - 1] == 'a') return true; return false; }
效率上也沒深入搞了,追求能用就行了.
那怎麼構建這個 char str[5] 呢. 這裡原本採用 5層for,這直接pass了,首先一條準則, C程式開發一定要記住,或者程式員也要記住
1 /* 2 用不用goto取決你的業務複雜度 3 4 */ 5 6 // 但是你一定不要用 超過三層的 迴圈,那種代碼寫出來後要打自己臉.
.後面採用 遞歸搞了一下, 如下
//採用遞歸演算法窮舉 void dgaa(char str[],int len,int idx, int *psum, int *pcut) { if (len > idx) { str[idx] = 'a'; dgaa(str, len, idx + 1, psum, pcut); str[idx] = 'b'; dgaa(str, len, idx + 1, psum, pcut); str[idx] = 'c'; return dgaa(str, len, idx + 1, psum, pcut); } ++*psum; *pcut += isaa(str, len); }
最後需要 return,因為到這裡就結束了,不能再往下了,否則重覆計數了. 大家有好方法可以分享.
到這裡一切都準備妥當了. 完整代碼如下:
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> // 串檢測函數 bool isaa(char str[], int len); //採用遞歸演算法窮舉 void dgaa(char str[], int len, int idx, int *psum, int *pcut); /* 上面函數的簡化巨集, 這裡 用法是 int psum = 0, pcut = 0; char str[5]; int cut = DGAA(str); */ #define DGAA(str, sum, cut) \ dgaa(str, sizeof(str)/sizeof(*str), 0, &sum, &cut) /* * 這裡處理一個問題 * 一個由abc組成的五位字元串,至少包含 一個連續aa的串有多少個. * */ int main(int argc, char* argv[]) { int sum = 0, cut = 0; char str[5]; DGAA(str, sum, cut); printf("所要找的所有串:%d個, 至少出現一次aa的串有 %d 個!\n",sum, cut); return 0; } // 串檢測函數 bool isaa(char str[], int len) { int i = 0; while(++i < len) if (str[i] == 'a' && str[i - 1] == 'a') return true; return false; } //採用遞歸演算法窮舉 void dgaa(char str[],int len,int idx, int *psum, int *pcut) { if (len > idx) { str[idx] = 'a'; dgaa(str, len, idx + 1, psum, pcut); str[idx] = 'b'; dgaa(str, len, idx + 1, psum, pcut); str[idx] = 'c'; return dgaa(str, len, idx + 1, psum, pcut); } ++*psum; *pcut += isaa(str, len); }
我們直接編譯鏈接一下
gcc -g -Wall -o aa.out aa.c
總的運行結果如下:
答案是 至少出現一次aa的串有 79 個.
第二部分 從更高觀點上分析這個問題
採用思路就是簡單的數學集合分析.
1) . abc 組成 長度為 5的串
一共有 3^5 = 81 x 3 = 243
2) . 沒有出現過 aa連續的串個數
A) 串中沒有a
2^5 = 32
B) 串中只有一個a
首先剩下4個位置 2^4 = 16 後面 一個a 插入 到 x|x |x |x |x
x的位置 有 C(1,5) = 5種,一共有 16 x 5 = 80種
C) 串中有兩個a x | x | x | x 左邊x的位置選出2個 插入 aa
一共有 2^3 x C(4,2) = 8 x 4 x 3 / 2 = 48種
D) 串中有3個 a 就是這樣情況 a | a | a
只有 2^2 = 4四種情況
綜上 A,B,C,D 一共有 32 + 80 + 48 + 4 = 112 + 52 = 164種
綜上1) 2) 得到至少一個aa連續出現的5位串 個數為
243 - 164 = 79 種
問題已經解決. 歡迎大家給出更巧妙的方法分享.
後記
到這裡說結束了, 錯誤是難免的,提出來一定改. 祝今天大家包括自己愉快, 以後的生活多一點行動,少一點
猶豫,關鍵是開心就好.O(∩_∩)O哈哈~
