數(shù)據(jù)結(jié)構(gòu)答案job2

2-1 設(shè)n個人圍坐在一個圓桌周圍，現(xiàn)在從第s個人開始報數(shù)，數(shù)到第m個人，讓他出局；然后從出局的下一個人重新開始報數(shù)，數(shù)到第m個人，再讓他出局，如此反復(fù)直到所有的人全部出局為止。下面要解決的Josephus問題是：對于任意給定的n, s和m，求出這n個人的出局序列。請以n = 9, s = 1, m = 5為例，人工模擬Josephus的求解過程以求得問題的解?！窘獯稹砍鼍秩说捻樞驗?, 1, 7, 4, 3, 6, 9, 2, 8。 2-2 試編寫一個求解Josephus問題的函數(shù)。用整數(shù)序列1, 2, 3, , n表示順序圍坐在圓桌周圍的人，并采用數(shù)組表示作為求解過程中使用的數(shù)據(jù)結(jié)構(gòu)。然后使用n = 9, s = 1, m = 5，以及n = 9, s = 1, m = 0，或者n = 9, s = 1, m = 10作為輸入數(shù)據(jù)，檢查你的程序的正確性和健壯性。最后分析所完成算法的時間復(fù)雜度?！窘獯稹亢瘮?shù)源程序清單如下：void Josephus( int A , int n, s, m ) int i, j, k, tmp;if ( m = 0 ) cout m = 0是無效的參數(shù)！ endl; return;for ( i = 0; i 1; i- ) /*逐個出局，執(zhí)行n-1次*/if ( i = k ) i = 0;i = ( i + m - 1 ) % k;/*尋找出局位置*/if ( i != k-1 ) tmp = Ai;/*出局者交換到第k-1位置*/ for ( j = i; j k-1; j+ ) Aj = Aj+1; Ak-1 = tmp;for ( k = 0; k n / 2; k+ ) /*全部逆置, 得到出局序列*/tmp = Ak; Ak = An-k+1; An-k+1 = tmp;例：n = 9, s = 1, m = 5 0 1 2 3 4 5 6 7 8k = 9 1 2 3 4 5 6 7 8 9第5人出局, i = 4k = 8 1 2 3 4 6 7 8 9 5第1人出局, i = 0k = 7 2 3 4 6 7 8 9 1 5第7人出局, i = 4k = 6 2 3 4 6 8 9 7 1 5第4人出局, i = 2k = 5 2 3 6 8 9 4 7 1 5第3人出局, i = 1k = 4 2 6 8 9 3 4 7 1 5第6人出局, i = 1k = 3 2 8 9 6 3 4 7 1 5第9人出局, i = 2k = 2 2 8 9 6 3 4 7 1 5第2人出局, i = 0 8 2 9 6 3 4 7 1 5第8人出局, i = 0逆置 5 1 7 4 3 6 9 2 8最終出局順序例：n = 9, s = 1, m = 0報錯信息 m = 0是無效的參數(shù)！例：n = 9, s = 1, m = 10 0 1 2 3 4 5 6 7 8k = 9 1 2 3 4 5 6 7 8 9第1人出局, i = 0k = 8 2 3 4 5 6 7 8 9 1第3人出局, i = 1k = 7 2 4 5 6 7 8 9 3 1第6人出局, i = 3k = 6 2 4 5 7 8 9 6 3 1第2人出局, i = 0k = 5 4 5 7 8 9 2 6 3 1第9人出局, i = 4k = 4 4 5 7 8 9 2 6 3 1第5人出局, i = 1k = 3 4 7 8 5 9 2 6 3 1第7人出局, i = 1k = 2 4 8 7 5 9 2 6 3 1第4人出局, i = 0 8 4 7 5 9 2 6 3 1第8人出局, i = 0逆置 1 3 6 2 9 5 7 4 8最終出局順序當(dāng)m = 1時，時間代價最大。達到( n-1 ) + ( n-2 ) + + 1 = n(n-1)/2 O(n2)。2-3 設(shè)有一個線性表 (e0, e1, , en-2, en-1) 存放在一個一維數(shù)組AarraySize中的前n個數(shù)組元素位置。請編寫一個函數(shù)將這個線性表原地逆置，即將數(shù)組的前n個原址內(nèi)容置換為 (en-1, en-2, , e1, e0)?！窘獯稹縯emplate void inverse ( Type A , int n ) Type tmp;for ( int i = 0; i j，數(shù)組元素Aij在數(shù)組B中沒有存放，可以找它的對稱元素Aji。在數(shù)組B的第 (2n-j) * (j-1) / 2 + i位置中找到。如果第0行第0列也計入，數(shù)組B從0號位置開始存放，則數(shù)組元素Aij在數(shù)組B中的存放位置可以改為當(dāng)i j時，= (2n-i+1) * i / 2 + j - i = ( 2n - i - 1 ) * i / 2 + j當(dāng)i j時，= (2n - j - 1) * j / 2 + i (3) 只存下三角部分時，若i j，則數(shù)組元素Aij前面有i-1行（1i-1，第0行第0列不算)，第1行有1個元素，第2行有2個元素，第i-1行有i-1個元素。在第i行中，第j號元素排在第j個元素位置，因此，數(shù)組元素Aij在數(shù)組B中的存放位置為1 + 2 + + (i-1) + j = ( i-1)*i / 2 + j若i j，數(shù)組元素Aij在數(shù)組B中沒有存放，可以找它的對稱元素Aji。在數(shù)組B的第 (j-1)*j / 2 + i位置中找到。如果第0行第0列也計入，數(shù)組B從0號位置開始存放，則數(shù)組元素Aij在數(shù)組B中的存放位置可以改為當(dāng)i j時，= i*(i+1) / 2 + j當(dāng)i j時，= j*(j+1) / 2 + i 2-10 設(shè)A和B均為下三角矩陣，每一個都有n行。因此在下三角區(qū)域中各有n(n+1)/2個元素。另設(shè)有一個二維數(shù)組C，它有n行n+1列。試設(shè)計一個方案，將兩個矩陣A和B中的下三角區(qū)域元素存放于同一個C中。要求將A的下三角區(qū)域中的元素存放于C的下三角區(qū)域中，B的下三角區(qū)域中的元素轉(zhuǎn)置后存放于C的上三角區(qū)域中。并給出計算A的矩陣元素aij和B的矩陣元素bij在C中的存放位置下標(biāo)的公式。【解答】計算公式2-14 字符串的替換操作replace (String &s, String &t, String &v)是指：若t是s的子串，則用串v替換串t在串s中的所有出現(xiàn)；若t不是s的子串，則串s不變。例如，若串s為“aabbabcbaabaaacbab”，串t為“bab”，串v為“abdc”，則執(zhí)行replace操作后，串s中的結(jié)果為“aababdccbaabaaacabdc”。試?yán)米址幕具\算實現(xiàn)這個替換操作?！窘獯稹縎tring & String : Replace ( String & t, String &v) if ( ( int id = Find ( t ) ) = -1 ) /沒有找到，當(dāng)前字符串不改，返回 cout The (replace) operation failed. endl; return *this; String temp( ch );/用當(dāng)前串建立一個空的臨時字符串 ch0 = 0; curLen = 0;/當(dāng)前串作為結(jié)果串，初始為空 int j, k = 0, l;/存放結(jié)果串的指針 while ( id != -1 ) for ( j = 0; j id; j+) chk+ = temp.chj;/摘取temp.ch中匹配位置id前面的元素到結(jié)果串ch。 curLen += id + v.curLen;/修改結(jié)果串連接后的長度 if ( curLen = maxLen ) l = v.curLen;/確定替換串v傳送字符數(shù)l else l = curLen - maxLen; curLen = maxLen; for ( j = 0; j l; j+ ) chk+ = v.chj;/連接替換串v到結(jié)果串ch后面 if ( curLen = maxLen ) break;/字符串超出范圍 for ( j = id + t.curLen; j temp.curLen; j+ ) temp.chj- id - t.curLen = temp.chj;/刪改原來的字符串 temp.curLen -= ( id + t.curLen ); id = temp.Find ( t ); return *this;2-15 編寫一個算法frequency，統(tǒng)計在一個輸入字符串中各個不同字符出現(xiàn)的頻度。用適當(dāng)?shù)臏y試數(shù)據(jù)來驗證這個算法?！窘獯稹拷y(tǒng)計算法include include string.hvoid frequency( String& s, char& A , int& C , int &k ) / s是輸入字符串，數(shù)組A 中記錄字符串中有多少種不同的字符，C 中記錄每/一種字符的出現(xiàn)次數(shù)。這兩個數(shù)組都應(yīng)在調(diào)用程序中定義。k返回不同字符數(shù)。int i, j, len = s.length( );if ( !len ) cout The string is empty. endl; k = 0; return; else A0 = s0; C0 = 1; k = 1; /*語句si是串的重載操作*/ for ( i = 1; i len; i+ ) Ci = 0; /*初始化*/ for ( i = 1; i len; i+ ) /*檢測串中所有字符*/ j = 0; while ( j k & Aj != si ) j+;/*檢查si是否已在A 中*/ if ( j = k ) Ak = si; Ck+; k+ /*si從未檢測過*/ else Cj+; /*si已經(jīng)檢測過*/ 測試數(shù)據(jù) s = cast cast sat at a tasa0測試結(jié)果 A c a s t b C 2 7 4 5 5【另一解答】include include string.hconst int charnumber = 128;/*ASCII碼字符集的大小*/void