不看会后悔的Windows XP之经验谈	简单快捷DIY实用家庭影院

求函数f(a,b)=2aa+b*b的100个最小函数值

楼主_Wanghui_（bingo）2005-05-19 22:18:01 在 C/C++ / C++ 语言提问

设计程序按从大到小的次序依次输出函数f(a,b)=2*a*a+b*b的最小的100个函数值及相应的两个参数的值，其中a和b均为自然数(包括0)。

最好先由小到大排列出，然后入栈，出栈

本以为很简单，想了想还真没好办法，要求时间复杂度尽可能底

请高手把算法说清楚点问题点数：100、回复次数：38Top

1 楼yesiloveyou（下意识的弯了一下腰,TMD,踩狗屎了）回复于 2005-05-19 22:46:52 得分 5

给个思路.

a,b为自然数
a=0,b=0;
a=0,b=1;
判断 if(b*b>2*a*a)a++;
即:
a=1,b=1;
再判断 else b++;
a=1,b=2;

a=2,b=2;
a=2,b=3;
a=3,b=3;
a=3,b=4;
a=3,b=5; //比如这边

while(numCount==100)exit;

Top

2 楼yesiloveyou（下意识的弯了一下腰,TMD,踩狗屎了）回复于 2005-05-19 22:48:04 得分 0

小错误
给个思路.

a,b为自然数
a=0,b=0;
判断 if(b*b>2*a*a)a++;
即:
a=0,b=1;
a=1,b=1;
再判断 else b++;
a=1,b=2;

a=2,b=2;
a=2,b=3;
a=3,b=3;
a=3,b=4;
a=3,b=5; //比如这边

while(numCount==100)exit;Top

3 楼ma100（）回复于 2005-05-19 22:50:38 得分 5

#include <stdio.h>

int fun ( int a , int b )
{
return 2*a*a + b;
}

void main()
{
int a=0;
int b=0;
int n=0;
int result[100], buf_a[100],buf_b[100];
while (a<200 && b<200 )
{
result[n] = 2*a*a + b*b;
buf_a[n] = a;
buf_b[n] = b;

if ( 2*(a+1)*(a+1 ) > (b+1 ) * (b+1 ) )
b++;
else
a++;
n++;
if ( n== 100 )
break;
}

for ( n=0;n<100;n++)
printf ( "%d:%d a %d b %d\n ",n,result[n],buf_a[n],buf_b[n]);

}Top

4 楼flyingdancing2005（返璞归C）回复于 2005-05-19 22:58:40 得分 0

还不明白Top

5 楼ma100（）回复于 2005-05-19 23:04:46 得分 0

int fun ( int a , int b )
{
return 2*a*a + b*b; 写错了
}
Top

6 楼yesiloveyou（下意识的弯了一下腰,TMD,踩狗屎了）回复于 2005-05-19 23:21:54 得分 0

回复人： flyingdancing2005() ( ) 信誉：100

不明白嘛/找个计算器算他100个看看/这方法应该可以搞定的Top

7 楼tfq（大梦谁先觉）回复于 2005-05-19 23:26:23 得分 0

从最小的a,b开始，逐渐增大a,b探索，每次必有一个步进1，2*(a+1)*(a+1 ) 与 (b+1 ) * (b+1 )的比较决定是a 增1还是b增1Top

8 楼10325（海上的云）回复于 2005-05-20 01:36:40 得分 0

不知道可不可以用两个for循环,一个嵌套在另外一个里面,分别使a和b从0开始循环
循环的退出条件就函数值>=100Top

9 楼_Wanghui_（bingo）回复于 2005-05-20 09:00:21 得分 0

楼上的各位，你们有没有考虑a=0，b=1，2，3，4，……的情况

还有b=0，a=1，2，3，……

ma100()给的程序前五个数据是0，1，3，6，12，17

但还应该是
0=2*0*0+0*0
1=2*0*0+1*1
2=2*1*1+0*0
3=2*1*1+1*1
4=2*0*0+2*2
6=2*1*1+2*2
……Top

10 楼_Wanghui_（bingo）回复于 2005-05-20 09:46:20 得分 0

顶一下Top

11 楼healer_kx（甘草(楼主揭贴吧，我们这些上班灌水的也不容易)）回复于 2005-05-20 10:15:32 得分 10

+之前是增函数
+只后也是

但是前面的递增速度快。
z =2a^2 + b^2是个啥图形啊？
截面是椭圆的抛物面。。。
？？大一的课忘得差不多了。。。

z值最小就是ab处于第一卦限内。。。
后面不会了。。。。
Top

12 楼mengzulin（Julian）回复于 2005-05-20 10:22:52 得分 5

1楼和2楼都对
假设：
a=a-1
b=a+1
则：
f(a,b)=2*a*a+b*b　＝　２(a-1)*(a-1)(a+1)*(a+1)
只要证明：
a*a*a*a<(a-1)*(a-1)(a+1)*(a+1) a>0

证明：
(a-1)*(a-1)(a+1)*(a+1)
=(a*a-2a+2)(a*a+2a+2)
= a*a*a*a +2a*a*a+2a*a - 2a*a*a-2a*a-4a+2a*a+4a+4
= a*a*a*a +2a*a+4

a*a*a*a<(a*a*a*a +2a*a+4)

Top

13 楼mengzulin（Julian）回复于 2005-05-20 10:26:23 得分 0

Sorry 看成f(a,b)=2*a*a*b*bTop

14 楼_Wanghui_（bingo）回复于 2005-05-20 10:50:14 得分 0

继续顶，求最佳算法Top

15 楼Rodge（三年了,还在摸索中）回复于 2005-05-20 11:01:57 得分 10

#include <iostream>
using namespace std;

int fun(int a,int b)
{
return 2*a*a+b*b;
}

void min(int a,int b,int n)
{
if(n >= 100)
return;

cout << "a is \t" << a << "\t b is \t" << b <<"\t fuc is \t"<<fun(a,b) << endl;

if(fun(a-1,b+1) < fun(a+1,b))
{
min(a-1,b+1,n+1);
}
else if(fun(a,b+1) < fun(a+1,b))
min(a,b+1,n+1);
else
min(a+1,b,n+1);
}

void main()
{
min(0,0,0);
}

不知道能不能满足楼主Top

16 楼_Wanghui_（bingo）回复于 2005-05-20 11:04:50 得分 0

前10个函数值
0，1，2，3，4，6，8，9，11，12
楼上的好像不行:(Top

17 楼Rodge（三年了,还在摸索中）回复于 2005-05-20 11:09:31 得分 0

不好意思，还是不对Top

18 楼c_nestor（）回复于 2005-05-20 11:10:29 得分 10

不用看就知道楼上不行
大家要搞清楚
不是只要考虑a++或者b++的情况的；
比如f( a, b ) = 75,// a = 5, b = 5;
这时候要考虑a = 0, f( a, b ) = 25;
还要考虑以前递增的时候中的较大者
因为以前的较大者现在可能又是较小者
感觉是一个麻烦的数学题
Top

19 楼_Wanghui_（bingo）回复于 2005-05-20 11:20:09 得分 0

楼上所言极是

这道题并不简单Top

20 楼_Wanghui_（bingo）回复于 2005-05-20 11:33:47 得分 0

我去吃个饭，回来再关注Top

21 楼andyli0418（小伟）回复于 2005-05-20 11:47:54 得分 0

有难度～～学习！　　顶！！Top

22 楼_Wanghui_（bingo）回复于 2005-05-20 12:40:02 得分 0

我加到100分了！
继续求助Top

23 楼healer_kx（甘草(楼主揭贴吧，我们这些上班灌水的也不容易)）回复于 2005-05-20 13:50:17 得分 0

接着看我前面的阐述，
图像在第一象限是一段椭圆。。。

Z的值是正整数【包括0】，取Z的值了，然后给定a【1。。n】求b就可以了。。。

Top

24 楼mostideal（三甲）回复于 2005-05-20 14:58:21 得分 5

顶。。高手继续呀。。。Top

25 楼Rodge（三年了,还在摸索中）回复于 2005-05-20 15:30:41 得分 10

一个不是办法的办法：

首先定义struct
{
int sum;
int a;
int b;
};

采集400个数据：
for(int a =0;a < 20; a++)
for(int b= 0;b <20; b++)
{
m_comb[i].a = a;
m_comb[i].b = b;
m_comb[i].sum = fun(a,b);
i++;
}
在用快速排序以sum排序，里面肯定会用相同的sum，从小到大取100不同的sum，相同的sum的a，b的组合当然也是要打印出来。

这种办法能够得到组合，只是太笨了。程序也就不贴了

结果组合是：
0 0 0
0 1 1
1 0 2
1 1 3
0 2 4
1 2 6
2 0 8
0 3 9
2 1 9
1 3 11
2 2 12
0 4 16
2 3 17
3 0 18
1 4 18
3 1 19
3 2 22
2 4 24
0 5 25
3 3 27
1 5 27
4 0 32
2 5 33
4 1 33
3 4 34
4 2 36
0 6 36
1 6 38
4 3 41
3 5 43
2 6 44
4 4 48
0 7 49
5 0 50
5 1 51
1 7 51
3 6 54
5 2 54
2 7 57
4 5 57
5 3 59
0 8 64
5 4 66
1 8 66
3 7 67
4 6 68
2 8 72
6 0 72
6 1 73
5 5 75
6 2 76
4 7 81
0 9 81
6 3 81
3 8 82
1 9 83
5 6 86
6 4 88
2 9 89
4 8 96
6 5 97
7 0 98
7 1 99
3 9 99
5 7 99
0 10 100
1 10 102
7 2 102
7 3 107
2 10 108
6 6 108
4 9 113
7 4 114
5 8 114
3 10 118
6 7 121
0 11 121
7 5 123
1 11 123
8 0 128
8 1 129
2 11 129
5 9 131
8 2 132
4 10 132
7 6 134
6 8 136
8 3 137
3 11 139
8 4 144
0 12 144
1 12 146
7 7 147
5 10 150
2 12 152
6 9 153
8 5 153
4 11 153
3 12 162
9 0 162
7 8 162
9 1 163
8 6 164
9 2 166
0 13 169
9 3 171
5 11 171
1 13 171
6 10 172
4 12 176
2 13 177
8 7 177
9 4 178
7 9 179
3 13 187
9 5 187
8 8 192
6 11 193
5 12 194
0 14 196
1 14 198
7 10 198
9 6 198
10 0 200
4 13 201
10 1 201
2 14 204
10 2 204
10 3 209
8 9 209
9 7 211
3 14 214
6 12 216
10 4 216
7 11 219
5 13 219
0 15 225
10 5 225

实际上a，b的循环只需到15就够了，不过放到20肯定不会错。
这上面刚好有100个不同的函数值，有138种a，b的组合。

希望有好办法出现！
Top

26 楼happy__888（[顾问团]寻开心 www.e-jjj.com）回复于 2005-05-20 15:49:32 得分 20

对于任何一个给定的数值y
y = 2*a*a + b *b
都是一个椭圆，考虑到ab都是取值自然数，那么就是第一象限的图像了

假定现在已经找到了一组ab是第n小的数值
那么我们在来找第n+1小的数值的时候可以按照如下的方法
根据 y = 2×an×an + bn×bn
我们来计算b取值0到sqrt（bn）时候的an的情况
b ＝ 0 1 2 .... sqrt(y)
a = sqrt(y*0.5) sqrt(y*0.5-0.5) sqrt(y*0.5-2) .... 0

显然下一组数据必然在这组数据的附近
把每个b所对应的a都上取整，然后用新的ab数值计算一组数值找最小的就是了
Top

27 楼happy__888（[顾问团]寻开心 www.e-jjj.com）回复于 2005-05-20 15:50:44 得分 0

最小数值也许会有多个，那就表示第n+1小的有多个并列的结果存在
Top

28 楼leng_qinjie（永远珍惜）回复于 2005-05-20 16:30:07 得分 0

#include <iostream>
using namespace std ;
void function(int count); // 此函数完成所需功能
int main()
{
function ( 100 );
cin.get();
return 0 ;
}
void function(int count)
{
static int a = 0;
static int b = 0;
count--;
if( count == 0 )
{
return ;
}
function ( count ) ;
cout << "a= " << a << " b= " << b
<< " 2*a*a+b*b= " << 2 * a * a + b * b << endl;
if( 4 * a + 2 < 2 * b + 1 )
{ a++ ; }
else { b++ ; }
}Top

29 楼leng_qinjie（永远珍惜）回复于 2005-05-20 16:32:35 得分 0

还未调试过
不过思想是对的
等我调试一会儿
好象有错Top

30 楼tfq（大梦谁先觉）回复于 2005-05-20 16:41:40 得分 15

/*从0开始步进，看看有没有两个数满足，没有继续步进*/
#include <stdio.h>
#include <conio.h>
#include <math.h>

void main()
{
int maxa=0,maxb=0,count=1,fun=0,a=0,b=0,flag=0;
while(count<=100)
{
maxa=sqrt(fun/2); /*a的最大值*/
maxb=sqrt(fun); /*b的最大值*/
for(b=0;b<=maxb;b++)
for(a=0;a<=maxa;a++)
{
if(2*a*a+b*b==fun)
{
printf("%d:fun=%d,a=%d,b=%d\n",count,fun,a,b);
flag=1; /*找到flag标志*/

}
else if(2*a*a+b*b>fun)
break;
}
fun++;
if(flag==1)
{
count++; /*fun 满足，计数增1*/
flag=0;
}
}
getch();
}

是笨了点，不过100个数内看不出慢哪里去，因为a,b的范围只在0到15之间
与回复人： Rodge(搞不懂) ( ) 信誉：96 2005-5-20 11:01:58 得分: 0
贴的一样。另问下TC下怎么输出窗口没滚动条啊，VC6下倒是有。Top

31 楼happy__888（[顾问团]寻开心 www.e-jjj.com）回复于 2005-05-20 16:59:55 得分 0

#include "stdio.h"
#include "stdlib.h"
#include "math.h"

#define MIN_N 138
int a[MIN_N];
int b[MIN_N];
int v[MIN_N];
main()
{
// ³õÊ¼»¯Ç°Èý¸ö
a[0]=b[0]=v[0] = 0;
a[1]=0, b[1]=1; v[1]=1;
a[2]=1, b[2]=0; v[2]=2;

// Ñ»·¼ÆËãÇ°100¸ö×îÐ¡µÄ
for ( int k=3; k<MIN_N; k++ )
{
int len = sqrt(v[k-1])+2;
int * pV = new int[len]; //
float * pA = new float[len]; //
for ( int tempB =0; tempB<len; tempB++ ) {
float v1 = ( v[k-1]+1 - tempB*tempB)*0.5;
if ( v1<0 )
pA[tempB] = MIN_N+1;
else
pA[tempB] = sqrt(v1);
pV[tempB] = 2*ceil(pA[tempB])*ceil(pA[tempB]) + tempB*tempB;
};

// ²éÕÒ×îÐ¡ÊýÖµÊÇ¼¸
int min = pV[0];
for ( int l=0; l<len; l++ ) {
if ( min>pV[l] ) min = pV[l];
};

// ²éÕÒÓÐ¼¸×éÏàÍ¬µÄ½â
int count = 0;
for ( l=0; l<len; l++ )
{
if ( min != pV[l] ) continue;
if ( count++ ) k++;
b[k] = l;
a[k] = ceil(pA[l]);
v[k] = pV[l];
}
delete [] pV;
delete [] pA;
};

// Êä³öÇ°100¸ö
for ( k=0; k<MIN_N; k++ )
{
printf("%03d: a=%2d, b=%2d, v=%3d\n", k+1, a[k], b[k], v[k]);
}
};Top

32 楼happy__888（[顾问团]寻开心 www.e-jjj.com）回复于 2005-05-20 17:01:16 得分 0

输出结果和 Rodge(搞不懂) 的一致
只要更改 MIN_N的定义，就可以控制输出的范围了
Top

33 楼fire314159（水源是学生，穷鬼，闷骚型男人的聚集地，请对号入座）回复于 2005-05-20 17:18:29 得分 0

从函数值入手，从1开始递增。然后用回溯法尝试能否找到合适的整数x,y。如果确定单是2*a*a都已经超过假设的值了，还没匹配，则该假设的值肯定不是我们要找的值，函数值加1，重新考察是否能找到匹配的x,y.设计数器count,每找到一个值，就加1，直到count==100，退出。Top

34 楼happy__888（[顾问团]寻开心 www.e-jjj.com）回复于 2005-05-20 17:18:50 得分 0

这种更直接

#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#include "conio.h"

#define MIN_N 138
main()
{
int min = 0; // 2*a*a+b*b 的数值
for (int k=1 ;k<=MIN_N; )
{
for ( int b=0; b<=sqrt(min); b++ ) // 直接用可能的b来循环
{
int temp = min - b * b;
if ( temp & 1 ) continue; // 2*a*a不可能是奇数
temp >>= 1; // a*a
int a = sqrt( temp);
if ( a * a == temp ) {
printf("%03d : a=%d, b=%d, v=%d\n", k, a, b, min);
k++;
};
}
min ++;
}
_getch();
};Top

35 楼martmy（白金汉公爵）回复于 2005-05-20 18:06:05 得分 5

直接搞定

const double sqr2 = sqrt(2);
int a = 0, b = 0;
int i = 100;
int str[100];

while(i>-1)
{
str[i] = 2*a*a+b*b;
if(b > sqr2*a)
a++;
else
b++;
i--;
}

Top

36 楼martmy（白金汉公爵）回复于 2005-05-20 18:17:02 得分 0

不好意思,有点考虑不周,
const double sqr2 = sqrt(2);
int a = 0, b = 0;
int i = 100;
int str[100];

while(i>-1)
{
str[i] = 2*a*a+b*b;
if(b+1 > sqr2*(a+1)) // 这里应该前向判定一下
a++,b--;
else
b++;
i--;
}Top

37 楼_Wanghui_（bingo）回复于 2005-05-20 23:35:41 得分 0

明天再详看，晚上宿舍熄灯Top

38 楼_Wanghui_（bingo）回复于 2005-05-24 22:43:38 得分 0

Roger给了两次10分，看错了Top

求函数f(a,b)=2*a*a+b*b的100个最小函数值