1331:求a在200以内满足a的立方等于b,c,d立方和的所有解。按a升序列出。
对于相同的a可能有符合的多种组合,要求按升序列出。
思路是多重循环遍历求解。
第一次写得代码如下:
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<memory.h>
#include<math.h>
#include<vector>
#include<algorithm>
using namespace std;
struct Cube
{
int a;
int b;
int c;
int d;
};
bool myorder(const Cube& s1,const Cube& s2)
{
if(s1.a != s2.a)
return s1.a < s2.a;
else if(s1.b != s2.b)
return s1.b < s2.b;
else
return s1.c < s2.c;
}
int a[201];
int b[201];
int c[201];
int d[201];
int cube[201];
vector<Cube> vcube;
int main()
{
double res;
int index;
int sum;
int vceil;
int vfloor;
//初始计算
for(int i=0;i<=200;i++)
cube[i]=i*i*i;
for(int bb=2;bb<=200;bb++)
for(int cc=bb;cc<=200;cc++)
for(int dd=cc;dd<=200;dd++)
{
sum=cube[bb]+cube[cc]+cube[dd];
res=pow(sum,1.0/3);
vceil = ceil(res);
vfloor = floor(res);
if(cube[vceil]==sum)
index=vceil;
else if(cube[vfloor]==sum)
index=vfloor;
else
index=-1;
if(index!=-1)
{
Cube c;
c.a=index;
c.b=bb;
c.c=cc;
c.d=dd;
vcube.push_back(c);
sort(vcube.begin(),vcube.end(),myorder);
}
}
for(int i=0;i<vcube.size();i++)
{
printf("Cube = %d, Triple = (%d,%d,%d)\n",vcube[i].a,vcube[i].b,vcube[i].c,vcube[i].d);
}
}
由于采用先得b,c,d再求a的方法,遇到了开方问题和排序问题。对于开方由于精度问题,原本的等式也可能不等。采用floor和ceil取整尝试。循环后自定义了排序方式进行排序。代码比较臃肿,运行效率低。
看到了一个好的写法如下
#include <stdio.h>
int BinarySearch(int s[], int high, int low, int key)
{
int mid;
while (low <= high) {
mid = (high + low) / 2;
if (s[mid] == key) return mid;
else if (s[mid] < key) low = mid + 1;
else high = mid - 1;
}
return 0;
}
int main(int argc, char *argv)
{
int a, b, c, d, i, cube[201];
for (i = 1; i < 201; i ++) cube[i] = i * i * i;
for (a = 6; a <= 200; a ++)
for (b = 2; b < a; b ++) {
i = cube[a] - cube[b];
for (c = b + 1; c < a; c ++) {
d = BinarySearch(cube, a - 1, c + 1, i - cube[c]);
if (d) printf("Cube = %d, Triple = (%d,%d,%d)\n", a, b, c, d);
}
}
return 0;
}
代码比较精简。两份代码都是采用了数组先将200以内所有数的立方值预先算好,由于需要多次使用,这样避免了重复计算。
主要的不同体现在循环的顺序以及验证等式的方法。采用已知a,b,c求d的方式。这样的好处是把a,b,c放在循环条件中,保持了升序。验证相等时没有采用开方,而是用了二分搜索,避免了浮点数处理。
在边界的处理上也体现了效率。如循环的上下界,搜索的上下界,这些都提升了效率。
分享到:
相关推荐
Interview,ZOJ,POJ 等平台。 欢迎Coders对代码加以指正和提议! 常见问题总结 两整数求平均值 average = min + (max - min) / 2 防止两整数的和越界 整数乘积对比 1.0 * m * m == num 类似乘积对比, 需转为double...
zoj网站中多个练习的c++解答,文件名即为题目序号。经本人测试可以使用,主要为动态规划方面的问题,希望给初学者提供帮助。
zoj 3590 -3+1.md
zoj 1140-zju 2433 简单题的部分答案 都是可以正确通过的,简洁易懂
算法刷题与练习 LeetCodeOJ-解决方案 欢迎访问作者的个人网站:
ZOJ完全解题报告,喜欢ACM的同学,欢迎下载
ZOJ题解集合-截至2835。共1244个文件,C/C++,有重复
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告
训练时发现的好题目。#include #include int main() { char ch; char str[100]; while(gets(str)) { if(str[0] == 'E') return 0; int z = 0, o = 0, j = 0, i = 0; while(str[i] !...}
zoj题目简单归类zoj题目简单归类zoj题目简单归类
zoj 3212 K-Nice.md
ZOJ 1055 Oh, Those Achin Feet.bfs求最短路径.
深度搜索 回溯 int main { string s1 s2; while cin >> s1 >> s2 { count 0; cout << "[" << endl; if s1 length s2 length BackTrake s1 s2 ;... [更多]
acm中zoj1002的可运行C++程序
zoj 2561 Order-Preserving Codes.md
包含了zoj700多道题目的源代码,在做题时可以参考
NULL 博文链接:https://weitch.iteye.com/blog/1006972
Problem Arrangement zoj 3777
ZOJ题目答案源码
一个非常非常非常非常实用的zoj结题代码