求花朵数的C/C++快速算法！！高手赐教！
一个N位的十进制正整数，如果它的每个位上的数字的N次方的和等于这个数本身，则称其为花朵数。
例如：
当N=3时，153就满足条件，因为 1^3 + 5^3 + 3^3 = 153，这样的数字也被称为水仙花数（其中，“^”表示乘方，5^3表示5的3次方，也就是立方）。
当N=4时，1634满足条件，因为 1^4 + 6^4 + 3^4 + 4^4 = 1634。
当N=5时，92727满足条件。
实际上，对N的每个取值，可能有多个数字满足条件。
程序的任务是：求N=21时，所有满足条件的花朵数。注意：这个整数有21位，它的各个位数字的21次方之和正好等于这个数本身。
如果满足条件的数字不只有一个，请从小到大输出所有符合条件的数字，每个数字占一行。因为这个数字很大，请注意解法时间上的可行性。要求程序在3分钟内运行完毕。
[解决办法]
strcpy(newBuf_1,*buf);
delete newBuf_2;
buf=&newBuf_1;
isb=0;
}
};
void StringBuffer::append(char *str)
{
long m_len=strlen(str);
if(m_len>remLen)
{
addBUF();
append(str);
return;
}
else
{
strcat(str);
remLen-=m_len;
}
};
void StringBuffer::strcat(char *str)
{
while((*(*buf+lastIndex)=*str++)!='\0')
lastIndex++;
};
char* StringBuffer::toString()
{
return *buf;
};
class NarcissusNumber {
private:
char number[21];
char lastNum[21];
int maxPos; //0
bool isNarc;
long powers[10];
long diff; //0
char diffDigits[22];
long totalDiff;
int step; //1
public:
void start(){
maxPos=0;
diff=0;
step=1;
}
int getDelta() {
return step;
}
int add(int delta) {
int i=0;
int x = delta;
totalDiff += x;
int pos = 0;
bool needCarry = false;
do {
diffDigits[pos] = number[pos];
number[pos] += x;
if (number[pos] > 9) {
number[pos] -= 10;
x = 1;
needCarry = true;
pos++;
} else {
// number[pos] += x;
needCarry = false;
}
} while (needCarry);
// refresh the max digit numbers
if (maxPos <= pos) {
// if total digit numbers changed, re-calculate the differ
diff = 0;
for (i = 0; i < maxPos; i++) {
diff -= powers[lastNum[i]];
}
maxPos = pos + 1;
for (i = 0; i < 10; i++) {
powers[i] *= i;
}
for (i = 0; i < maxPos; i++) {
diff += powers[number[i]];
}
} else {
for (i = 0; i <= pos; i++) {
diff += (powers[number[i]] - powers[diffDigits[i]]);
}
}
long b = totalDiff - diff;
cout<<getNumberString()<<", new diff="<<diff<<", b="<<(b)<<endl;
isNarc = b == 0;
if (isNarc) {
step = (number[0] == 0 ? 1 : 10 - number[0]);
for (int i = 0; i < maxPos; i++) {
lastNum[i] = number[i];
}
diff = 0;
totalDiff = 0;
} else {
if (number[0] != 0) {
step = 1;
} else {
step = 10;
int s = 1;
int e = 9;
while (s <= e) {
int p = (s + e) >> 1;
long val = powers[p] - p;
if (b == val) {
step = p;
break;
} else if (b < val) {
e = p - 1;
} else {
s = p + 1;
}
}
}
}
return maxPos;
}
char getNumberString() {
StringBuffer result((char *)maxPos);
for (int i = maxPos - 1; i >= 0; i--) {
result.append((char *)number[i]);
}
return (char)result.toString();
}
bool isNarcissus() {
return isNarc;
}
void init(long seed, int n){
maxPos = n;
for (int i = 0; i < n; i++) {
lastNum[i] = number[i] = (char) (seed % 10);
seed /= 10;
}
isNarc = true;
for (i = 0; i < 10; i++) {
powers[i] = (long)pow(i, n);
}
totalDiff = 0;
}
};
void main(void) {
int n = 3;
long seed = 153;
NarcissusNumber num;
num.start();
num.init(seed, n);
int delta = 1;
long val = seed;
char cc;
while (n < 22) {
if (num.isNarcissus()) {
cc=num.getNumberString();
printf("%s",&cc);
}
delta = num.getDelta();
n = num.add(delta);
}
}
[解决办法]
我写的，但是速度很慢，到7位的时候已经20s左右，如果到21位得几千万年...
/**
* 一个N位的十进制正整数，如果它的每个位上的数字的N次方的和等于这个数本身，则称其为花朵数。
例如：
当N=3时，153就满足条件，因为 1^3 + 5^3 + 3^3 = 153，这样的数字也被称为水仙花数（其中，“^”表示乘方，5^3表示5的3次方，也就是立方）。
当N=4时，1634满足条件，因为 1^4 + 6^4 + 3^4 + 4^4 = 1634。
当N=5时，92727满足条件。
实际上，对N的每个取值，可能有多个数字满足条件。
程序的任务是：求N=21时，所有满足条件的花朵数。注意：这个整数有21位，它的各个位数字的21次方之和正好等于这个数本身。
如果满足条件的数字不只有一个，请从小到大输出所有符合条件的数字，每个数字占一行。因为这个数字很大，请注意解法时间上的可行性。要求程序在3分钟内运行完毕。
*/
package edu.excise.kaoshi;
import java.math.BigInteger;
import java.util.ArrayList;
public class Test10
{
public static final int SIZE = 24;
public static void main(String[] args)
{
MyStack myStack = new MyStack();
// String sStart = "10000000000";
// String sEnd = "99999999999";
String sStart = "1000000000";
String sEnd = "9999999999";
String mubiao;
int[] arr = new int[SIZE];
int[] sum = new int[SIZE];
int jieQu = 0;// 用来删除数组前n为零，以便与s比较
ArrayList list = new ArrayList();
BigInteger start = new BigInteger(sStart);
BigInteger end = new BigInteger(sEnd);
BigInteger ONE = new BigInteger("1");
for (BigInteger i = start; i.compareTo(end) < 0; i = i.add(ONE))
{
String s = i.toString();
mubiao = "";
// System.out.println(s + "的各项和为:");
// 入栈
for (int i1 = 0; i1 < s.length(); i1++)
{
myStack.push(s.charAt(i1));
}
// 出栈，进入数组
for (int i2 = myStack.index; i2 >= 0; i2--)
{
arr[SIZE - s.length() + i2] = myStack.pop();
}
// 求出次幂，并加入list，准备求加法
for (int i3 = 0; i3 < SIZE; i3++)
{
list.add(power(arr[i3], s.length()));
}
// 开始求和并且把list滞空，以便后面的数字调用
sum = getSum(list);
list.clear();
//获得求和后数组，并且截取前n为0，字符串
for (int i4 = 0; i4 < sum.length; i4++)
{
if (sum[i4] == 0)
{
} else
{
jieQu = i4;
break;
}
}
for (int i5 = jieQu; i5 < sum.length; i5++)
{
mubiao = mubiao + sum[i5];
}
//判断是否是花朵数
if (mubiao.equals(s))
{
System.out.println(s + "是一个花朵数字");
}
}
System.out.println("程序执行完毕");
}
public boolean isHuaDuoShu()
{
return false;
}
// 求21项的和
public static int[] getSum(ArrayList list)
{
int[] sum = new int[SIZE];
for (int i = 0; i < list.size(); i++)
{
sum = add(sum, (int[]) list.get(i));
// System.out.print("每次加完后的和为");
// for (int i5 = 0; i5 < sum.length; i5++)
// {
// System.out.print(sum[i5]);
// }
// System.out.println();
}
return sum;
}
// 每项的加法
public static int[] add(int sum[], int arr[])
{
int jinwei = 0;
for (int i = sum.length; i > sum.length - arr.length; i--)
{
int x = sum[i - 1] + arr[arr.length - sum.length + i - 1];
// 如果乘出的结果大于9，进位
if (x + jinwei > 9)
{
// 先用进位计算了本位结果之后，再赋给新的进位值
sum[i - 1] = (x + jinwei) % 10;
jinwei = (x + jinwei) / 10;
} else
{
sum[i - 1] = x + jinwei;
jinwei = 0;
}
}
return sum;
}
// 求幂次方
public static int[] power(int jishu, int zhishu)
{
int j = SIZE;// 数组大小
int jinwei = 0;// 防止相加的时机过早，加上这个参数
int[] arr = new int[j];// 数组
// for (int m = 0; m < SIZE; m++)
// arr[m] = 0;// 初始化
// 当指数为9时，刚传入，数组为空，先将最后一位赋值。
// i代表多少次方，j代表数组索引
for (int i = zhishu; i > 0; i--)
{
// 当第一次进入，复制
if (zhishu == i)
{
arr[j - 1] = jishu;
} else
{
// 进入循环，开始乘，遍历数组没一个元素
for (int p = SIZE; p > 0; p--)
{
// 每一位和基数乘后的值
int x = (arr[p - 1]) * jishu;
// 如果乘出的结果大于9，进位
if (x + jinwei > 9)
{
// 先用进位计算了本位结果之后，再赋给新的进位值
arr[p - 1] = (x + jinwei) % 10;
jinwei = (x + jinwei) / 10;
} else
{
arr[p - 1] = x + jinwei;
jinwei = 0;
}
}
}
}
return arr;
}
// 判断是否相等
public static boolean compareTo(int a[], int b[])
{
if (a.length == b.length)
{
for (int i = 0; i < a.length; i++)
{
if (a[i] != b[i])
{
return false;
}
}
} else
{
return false;
}
return true;
}
}
class MyStack
{
int[] arr = new int[Test10.SIZE];
int index = -1;
BigInteger num;
void push(char ch)
{
index++;
arr[index] = ch - 48;
}
int pop()
{
return arr[index--];
}
int getTop()
{
return arr[index];
}
}
*/
private void setValue(int num) {
countArray[offset] = num;
if (offset == 0) {
countSumArray[offset] = num;
sumArray[offset] = p(9 - offset).multiply(n(num));
} else {
countSumArray[offset] = countSumArray[offset - 1] + num;
sumArray[offset] = sumArray[offset - 1].add(p(9 - offset).multiply(n(num)));
}
}
/**
* 检验当前数据是否匹配
*
* @return
*/
private boolean checkPersentArray() {
BigInteger minVal = sumArray[offset];// 当前已存在值
BigInteger maxVal = sumArray[offset].add(p(9 - offset).multiply(n(SIZE - countSumArray[offset])));// 当前已存在值+可能存在的最大值
// 最小值匹配
if (minVal.compareTo(MAX) > 0) {
return false;
}
// 最大值匹配
if (maxVal.compareTo(MIN) < 0) {
return false;
}
String minStr = minVal.compareTo(MIN) > 0 ? minVal.toString() : MIN.toString();
String maxStr = maxVal.compareTo(MAX) < 0 ? maxVal.toString() : MAX.toString();
// 找到最小值与最大值间首部相同的部分
int[] sameCountArray = new int[10];
for (int i = 0; i < SIZE; i++) {
char c;
if ((c = minStr.charAt(i)) == maxStr.charAt(i)) {
sameCountArray[c - '0'] = sameCountArray[c - '0'] + 1;
} else {
break;
}
}
// 判断如果相同部分有数据大于现在已记录的位数，返回false
for (int i = 0; i <= offset; i++) {
if (countArray[i] < sameCountArray[9 - i]) {
return false;
}
}
// 如果当前值的总数为SIZE位，那么判断该值是不是需要查找的值
if (countSumArray[offset] == SIZE) {
String sumStr = sumArray[offset].toString();
BigInteger sum = ZERO;
for (int i = 0; i < sumStr.length(); i++) {
sum = sum.add(p(sumStr.charAt(i) - '0'));
}
return sum.compareTo(sumArray[offset]) == 0;
}
return true;
}
/**
* 退出循环，打印
*
* @return
*/
private void success() {
System.out.println("find a match number:" + sumArray[offset]);
}
/**
* 将浮标指向下一位数
*
* @return
*/
private void next() {
offset++;
setValue(SIZE - countSumArray[offset - 1]);
}
/**
*
* 回退浮标，找到最近的浮标，并减一
*
* @return
*/
private boolean back() {
// 回退浮标，找到最近的浮标，并减一
if (countArray[offset] == 0) {
while (countArray[offset] == 0) {
if (offset > 0) {
offset--;
} else {
return true;
}
}
}
if (offset > 0) {
setValue(countArray[offset] - 1);
return false;
} else {
return true;
}
}
/**
* 测试程序
*
* @param startValue
* 测试匹配数中包含9的个数
* @param startTime
* 程序启动时间
*/
private void test(int startValue, long startTime) {
// 设置9的个数
offset = 0;
setValue(startValue);
while (true) {
if (checkPersentArray()) {// 检查当前提交数据是否匹配
// 匹配且总数正好为SIZE的位数，那么就是求解的值
if (countSumArray[offset] == SIZE) {
success();
}
// 总数不为SIZE，且当前值不在第10位（即不等于0）
if (offset != 9) {
next();
continue;
}
// 总数不为SIZE，且当前值在第10位。
if (back()) {
break;
}
} else {
if (back()) {
break;
}
}
}
System.out.println(Thread.currentThread() + " End,Spend time " + (System.currentTimeMillis() - startTime) / 1000 + "s");
}
/**
* 主函数
*/
public static void main(String[] args) {
final long startTime = System.currentTimeMillis();
int s = MAX.divide(p(9)).intValue();
for (int i = 0; i <= s; i++) {
// new Main().test(i, startTime);
// 启动十个线程同时运算
final int startValue = i;
new Thread(new Runnable() {
public void run() {
new Main().test(startValue, startTime);
}
}).start();
}
}
private static final BigInteger ZERO = new BigInteger("0");
private static final BigInteger MIN;
private static final BigInteger MAX;
/**
* 0-SIZE间的BigInteger
*/
private static final BigInteger n(int i) {
return (BigInteger) ht.get("n_" + i);
}
/**
* 0-9的次方的BigInteger
*/
private static final BigInteger p(int i) {
return (BigInteger) ht.get("p_" + i);
}
/**
* 用于缓存BigInteger数据，并初始化0-SIZE间的BigInteger和0-9的次方的BigInteger
*/
private static Hashtable<String, Object> ht = new Hashtable<String, Object>();
static {
int s = SIZE < 10 ? 10 : SIZE;
for (int i = 0; i <= s; i++) {
ht.put("n_" + i, new BigInteger(String.valueOf(i)));
}
for (int i = 0; i <= 10; i++) {
ht.put("p_" + i, new BigInteger(String.valueOf(i)).pow(SIZE));
}
MIN = n(10).pow(SIZE - 1);
MAX = n(10).pow(SIZE).subtract(n(1));
}
}
哎看不懂！
