求算法设计与分析的小程序

发布网友 发布时间：2022-05-06 04:26

我来回答

共1个回答

热心网友 时间：2022-06-28 17:41

visual studio下的工程，所以有个预编译头stdafx，然后没考虑异常。。
stdafx应该是去掉就可以吧，我不太清楚，反正这个根据vc++的情况稍作改动就可以了，其他算法之类是不受影响的
---------------------------------------------------------
输入两个数，当中要有一个空格。不过C/C++实在写的太少，貌似读入那里写的太麻烦了。。但是又不知道一般会怎么写。。然后，异常依旧未考虑。。

#include "stdafx.h"
#include "stdio.h"

double result = 10e250;
int *plusPositions;
int plusCount;

double atod(int *digits, int length)
{
double number = 0;
for (int i = 0; i < length; ++i) {
number = number * 10 + digits[i];
}
return number;
}

void solve(int *digits, int length, int index, double currentSum,
int plusesRemain, int *tempPlusPositions)
{
if (plusesRemain == 0) {
double tempResult = currentSum + atod(digits, length);
if (tempResult < result) {
memcpy(plusPositions, tempPlusPositions, sizeof(int) * plusCount);
result = tempResult;
}
} else {
for (int i = 1; i < length - plusesRemain + 1; ++i) {
tempPlusPositions[plusesRemain - 1] = index + i;
solve(digits + i, length - i, index + i,
currentSum + atod(digits, i), plusesRemain - 1,
tempPlusPositions);
}
}
}

inline void printResult(int *digits, int length)
{
int digitIndex = 0, plusIndex;
for (plusIndex = plusCount - 1; plusIndex >= 0; --plusIndex) {
for ( ; digitIndex < plusPositions[plusIndex]; ++digitIndex) {
printf("%d", digits[digitIndex]);
}
printf(" + ");
}
for ( ; digitIndex < length; ++digitIndex) {
printf("%d", digits[digitIndex]);
}
printf(" = %d\n", (int) result);
}

void solve(int *digits, int length, int pluses)
{
plusCount = pluses;
plusPositions = new int[pluses];
int *tempPlusPositions = new int[pluses];
solve(digits, length, 0, 0, pluses, tempPlusPositions);
printResult(digits, length);
delete [] tempPlusPositions;
delete [] plusPositions;
}

int _tmain(int argc, _TCHAR* argv[])
{
char string[200];
int digits[200], plus;
scanf("%s %d", &string, &plus);
int i;
char c;
for (i = 0; i < 200; ++i) {
c = string[i];
if (c == '\0')
break;
digits[i] = c - '0';
}
solve(digits, i, plus);

return 0;
}