题解 | #尼科彻斯定理#
尼科彻斯定理
http://www.nowcoder.com/practice/dbace3a5b3c4480e86ee3277f3fe1e85
题目的主要信息:
验证尼科彻斯定理,即:任何一个整数m的立方都可以写成m个连续奇数之和。输入一个正整数m(m≤100),将m的立方写成m个连续奇数之和的形式输出。
方法一:
用value保存num的立方,将1-num^3之间所有奇数保存到vec中。根据题意,遍历一遍所有奇数,每次奇数以该奇数开头的连续num个奇数之和,如果和等于value就说明找到了一组num个连续的奇数,输出这一组奇数。
具体做法:
#include<bits/stdc++.h>
using namespace std;
int main() {
int num; //num为输入的正整数
while(cin>>num) {
vector<int> vec;//容器vec保存1~num^3之间的所有奇数
int value = pow(num, 3);//value的值为num的立方
for(int i=1;i<=value;i++) {//将1~num^3之间的所有奇数保存容器vec中
if(i%2)//如果是奇数,存入vec中
vec.push_back(i);
}
for(int i=0;i<=vec.size()-num;i++) {//遍历一遍所有奇数
int sum=0;
for(int j=i;j<i+num;j++)//sum计算num个连续奇数之和
sum+=vec[j];
if(sum==value) {//如果sum==value,说明找到了这样的一组num个连续的奇数
for(int j=i;j<i+num;j++) {//输出这一组奇数
if(j==i+num-1)
cout<<vec[j]<<endl;
else
cout<<vec[j]<<"+";
}
break;//找到一组奇数,结束循环
}
}
}
return 0;
}
复杂度分析:
- 时间复杂度:,两层for循环。
- 空间复杂度:,借用vec存储所有奇数。
方法二:
找规律,第一个奇数总是为num*(num-1)+1,然后再输出剩余的num-1个奇数。
具体做法:
#include <iostream>
using namespace std;
int main() {
int a,b,i;
while (cin >> a ) {
b=a*(a-1)+1;//确定第一个数
for(i=0;i<a-1;i++) {//依次输出后面的a-1个数
cout<<b+2*i<<'+';
}
cout<<b+2*i<<endl;
}
}
复杂度分析:
- 时间复杂度:,需要遍历一遍输出n-1个数。
- 空间复杂度:,只用了常数空间。