owNo][iColNo]==0) {
Grid[iRowNo][iColNo] = 1;
iSumR[iRowNo]++; iSumC[iColNo]++; if(iSumR[iRowNo]
Set(iRowNo);
else if(iSumR[iRowNo]==iPointsR[iRowNo] && iRowNo < ROWS)
Set(iRowNo + 1);
Grid[iRowNo][iColNo] = 0;
iSumR[iRowNo]--;
iSumC[iColNo]--;
}
}
}
return iFound; // 用于判断是否有解
}
int main(int argc, char* argv[]) {
if(!Set(0))
printf("Failure!");
}
9、有4种面值的邮票很多枚，这4种邮票面值分别1, 4, 12, 21，现从多张中最多任取5张进行组合，求取出这些邮票的最大连续组合值。（据说是华为2003年校园招聘笔试题）
#define N 5
#define M 5
int k, Found, Flag[N];
int Stamp[M] = {0, 1, 4, 12, 21};
// 在剩余张数n中组合出面值和Value
int Combine(int n, int Value) {
if(n >= 0 && Value == 0) {
Found = 1;
int Sum = 0;
for(int i=0; i
Sum += Stamp[Flag[i]];
printf("%d ", Stamp[Flag[i]]);
}
printf("\tSum=%d\n\n", Sum);
}else for(int i=1; i
0; i++)
if(Value-Stamp[i] >= 0) {
Flag[k++] = i;
Combine(n-1, Value-Stamp[i]);
Flag[--k] = 0;
}
return Found;
}
int main(int argc, char* argv[]) {
for(int i=1; Combine(N, i); i++, Found=0);
}
10、大整数数相乘的问题。（这是2002年在一考研班上遇到的算法题）
void Multiple(char A[], char B[], char C[]) {
int TMP, In=0, LenA=-1, LenB=-1;
while(A[++LenA] != ‘\0′);
while(B[++LenB] != ‘\0′);
int Index, Start = LenA + LenB – 1;
for(int i=LenB-1; i>=0; i–) {
Index = Start–;
if(B[i] != ’0′) {
for(int In=0, j=LenA-1; j>=0; j–) {
TMP = (C[Index]-’0′) + (A[j]-’0′) * (B[i] – ’0′) + In;
C[Index--] = TMP % 10 + ’0′;
In = TMP / 10;
}
C[Index] = In + ’0′;
}
}
}
int main(int argc, char* argv[]) {
char A[] = “21839244444444448880088888889″;
char B[] = “38888888888899999999999999988″;
char C[sizeof(A) + sizeof(B) - 1];
for(int k=0; k
C[k] = '0';
C[sizeof(C)-1] = '\0';
Multiple(A, B, C);
for(int i=0; C[i] != '\0'; i++)
printf("%c", C[i]);
}
11、求最大连续递增数字串（如“ads3sl456789DF3456ld345AA”中的“456789”）
int GetSubString(char *strSource, char *strResult) {
int iTmp=0, iHead=0, iMax=0;
for(int Index=0, iLen=0; strSource[Index]; Index++) {
if(strSource[Index] >= ’0′ && strSource[Index] <= '9' &&
strSource[Index-1] > ’0′ && strSource[Index] == strSource[Index-1]+1) {
iLen++; // 连续数字的长度增1
} else { // 出现字符或不连续数字
if(iLen > iMax) {
iMax = iLen; iHead = iTmp;
}
// 该字符是数字，但数字不连续
if(strSource[Index] >= ’0′ && strSource[Index] <= '9') {
iTmp = Index;
iLen = 1;
}
}
}
for(iTmp=0 ; iTmp < iMax; iTmp++) // 将原字符串中最长的连续数字串赋值给结果串
strResult[iTmp] = strSource[iHead++];
strResult[iTmp]='\0';
return iMax; // 返回连续数字的最大长度
}
int main(int argc, char* argv[]) {
char strSource[]="ads3sl456789DF3456ld345AA", char strResult[sizeof(strSource)];
printf("Len=%d, strResult=%s \nstrSource=%s\n",
GetSubString(strSource, strResult), strResult, strSource);
}
12、四个工人，四个任务，每个人做不同的任务需要的时间不同，求任务分配的最优方案。（2005年5月29日全国计算机软件资格水平考试——软件设计师的算法题）。
#include "stdafx.h"
#define N 4
int Cost[N][N] = { {2, 12, 5, 32}, // 行号：任务序号，列号：工人序号
{8, 15, 7, 11}, // 每行元素值表示这个任务由不同工人完成所需要的时间
{24, 18, 9, 6},
{21, 1, 8, 28}};
int MinCost=1000;
int Task[N], TempTask[N], Worker[N];
void Assign(int k, int cost) {
if(k == N) {
MinCost = cost;
for(int i=0; i
TempTask[i] = Task[i];
} else {
for(int i=0; i
if(Worker[i]==0 && cost+Cost[k][i] < MinCost) { // 为提高效率而进行剪枝
Worker[i] = 1; Task[k] = i;
Assign(k+1, cost+Cost[k][i]);
Worker[i] = 0; Task[k] = 0;
}
}
}
}
int main(int argc, char* argv[]) {
Assign(0, 0);
printf("最佳方案总费用=%d\n", MinCost);
for(int i=0; i
printf("\t任务%d由工人%d来做：%d\n", i, TempTask[i], Cost[i][TempTask[i]]);
}
13、八皇后问题，输出了所有情况，不过有些结果只是旋转了90度而已。（回溯算法的典型例题，是数据结构书上算法的具体实现，大家都亲自动手写过这个程序吗？）
#define N 8
int Board[N][N];
int Valid(int i, int j) { // 判断下棋位置是否有效
int k = 1;
for(k=1; i>=k && j>=k;k++)
if(Board[i-k][j-k]) return 0;
for(k=1; i>=k;k++)
if(Board[i-k][j])