问题求解06递归.pptVIP

木棍问题 设 f (k, left, L, N) 表示能否将 k 根木棒拼成 N 根长度是 L 的木棒加一根长度是 left 的木棒。这个left 表示当前正在拼的一根木棒。 从 k 根木棒里从大到小寻找一根长度为 t 并且 t 小于等于 left 的木棒，将它拼入当前正在拼的木棒，则原问题化成 f (k-1, left-t, L, N) ， 即能否将 k-1 根木棒拼成 N 根长度是 L 的木棒加一根长度是 left-t 的木棒。 随着递归层次的加深，k 会不断地减小直到等于0。如果当 k 递归到 0 时，left==N==0，则表示可以将 k 根木棒拼成 N 根长度是 L 的木棒加一根长度是 left 的木棒。 如果在递归的过程中出现从 k 根木棒里找不到长度小于等于 left 的木棒，则表明这条递归的道路不通，需要回到上一层，将已经拼到半路的木棒从末尾拆掉一根，换用新的一根再继续尝试。 需要说明的是当 left==0 时，将 left 置成 L，并将 N 的值减 1。表明已经成功拼出一根程度是 L 的木棒，准备拼下一根长度是 L 的木棒。 木棍问题 bool concatenate(int totalSticks, int unusedSticks, int left, int len) //递归函数，判断某个长度是否是木棒可能的原始长度 // totalSiticks 是木棒的总数， // unusedSticks 是未被拼到长度为len 的原始木棒中的木棒数目 // left 是当前正在拼得木棒的剩余长度 // len 是正在尝试的原始木棒长度 int compare( const void *arg1, const void *arg2 ) // 为qsort 准备的比较函数 { return *(int *)arg2 - *(int *)arg1; } int sticks[100]; //记录每个木棒的长度，按长度降序排列 bool used[100]; //记录木棒被使用的情况 木棍问题——main() scanf(%d, n); while(n != 0) { int i, sum = 0, len; //sum 是所有木棒的总长度 for(i = 0; i n; i++){ //初始化，读入木棒长度 used[i] = false; scanf(%d, (sticks[i])); sum += sticks[i]; } qsort(sticks, n, sizeof(int), compare); //将木棒按长度降序排列 len = sticks[0]; //len 的最小可能取值等于木棒中最长的一段 for(i = len; i = sum; i++) { //按升序枚举木棒的可能长度 if (sum % i != 0 ) continue; if ( concatenate(n, n, 0, i) ) { printf(%d\n, i); break; } } scanf(%d, n); } 木棍问题 bool concatenate(int totalSticks, int unusedSticks,int left, int len) { int i; if(unusedSticks == 0 left == 0) return true; if(left == 0) left = len; for(i=0; i totalSticks; i++){ if(used[i] == true) continue; if(sticks[i] left) continue; used[i] = true; if(concatenate(totalSticks, unusedSticks - 1, left - sticks[i], len)) return true; used[i] = false; if(sticks[i] == left || left == len) break; } return false; } 思考题 A,B,C,D,E共5个人合伙夜间捕鱼，清晨时都疲倦不堪，各自在河边的树丛中睡着了。日上三竿，A第一个醒来，他将鱼平分为5份，把多余的一条扔回河中，拿着自己的一份回家了。B第二个醒来，也将鱼平分为5份，扔掉多余的一条，拿走自己的一份。接着C、D、E依次醒来，也都按此办理。问：5个人至少