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

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