求花朵数的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分钟内运行完毕。
[解决办法]
[code=C/C++][/code]#ifndef _STRINGBUFFER_H_
#define _STRINGBUFFER_H_
#endif
#include<iostream>
#include <stdlib.h>
#include <malloc.h>
#include <string>
#include<math.h>
#include <stdlib.h>
using namespace std;
class StringBuffer
{
private:
char* *buf,*newBuf_1,*newBuf_2;
long initSize,bufLen,remLen,lastIndex;
void init();
void addBUF();
int isb,isf;
void strcat(char *);
public:
StringBuffer();
StringBuffer(char *str);
void append(char* str);
char* toString();
};
StringBuffer::StringBuffer()
{
init();
};
StringBuffer::StringBuffer(char *str)
{
init();
strcat(str);
remLen=bufLen-strlen(str);
};
void StringBuffer::init()
{
initSize=51200;
newBuf_1=new char[initSize];
memset(newBuf_1,0,initSize);
buf=&newBuf_1;
bufLen=initSize;
remLen=initSize-1;
isb=0;
isf=1;
lastIndex=0;
};
void StringBuffer::addBUF()
{
if(bufLen<524288)
{
remLen+=bufLen*2;
bufLen=bufLen+bufLen*2;
}
else
{
bufLen=bufLen+524288;
remLen+=524288;
}
if(isb==0)
{
newBuf_2=new char[bufLen];
strcpy(newBuf_2,*buf);
delete newBuf_1;
buf=&newBuf_2;
isb=1;
return;
}
else
{
newBuf_1=new char[bufLen];
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]; }}
[解决办法]
普通算法 求高效算法 ？？？？？？？？？？？？？？？？
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
void flower(int *,float,float,int);
void main()
{
time_t timep;
struct tm *p;
//---------开始时间--------------------
time(&timep); /*取得当地时间*/
p=localtime(&timep); /*转换时间*/
printf("开始时间：%d:%d\n" ,p->tm_min,p->tm_sec);
//------------------------------------------
int array[4]={0,0,0,0};//,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
float temp1=0,temp2=0;
int conter=1;
for(int i=1;i<10;i++)
{
array[0]=i;
flower(array,temp1,temp2,conter);
}
//----------------------------------------------
time(&timep); /*取得当地时间*/
p=localtime(&timep); /*转换时间*/
printf("\n结束时间 %d:%d\n",p->tm_min,p->tm_sec);
system("pause");
}
void flower(int *array,float temp1,float temp2,int conter)
{
conter++;
if(5==conter)
{
for(int n=0,m=4;n<4;n++,m--)
{
temp1+=pow(array[n],4);
temp2+=pow(10,m-1)*array[n];
}
if(temp2==temp1)
printf("%4.0f\n",temp1);
return;
}
for(int i=0;i<10;i++)
{
array[conter-1]=i;
flower(array,temp1,temp2,conter);
}
return;
}
[解决办法]
package com.jcq;
import java.math.BigInteger;
import java.util.Hashtable;
public class Main {
private static final int SIZE = 21;
private int[] countArray = new int[10]; // 个数列表
private int[] countSumArray = new int[10]; // 个数总数
private BigInteger[] sumArray = new BigInteger[10];// 值总数
private int offset = 0;// 浮标
/**
* 设置当前浮标对应的个数，个数的总数，值总数
*
* @param num
* 个数
*/
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));
}
}
哎看不懂！