【题解】平方和
本文最后更新于 1097 天前,其中的信息可能已经有所发展或是发生改变。

描述
验证某个正整数m是否可以表示成若干个互不相同正整数的平方和
输入
一个正整数n,表示有n组案例。
每组案例由一个正整数m组成。(m<=1000000)
输出
针对每组案例,如果m能表示成多个(可以是一个,也可以不止一个)互不相同整数的平方和,那么输出Yes,否则输出No。
每组案例输出完都要换行。
样例输入
3
14
15
16
样例输出
Yes
No
Yes
HINT
14=1*1+2*2+3*3 16=4*4

本题为dfs模板题

int f(int num, int start)
{
	if (num < 0)return false;//num小于0,平方和已超出num
	if (num == 0)return true;//num等于0,平方和正好等于num
	for (int i = start + 1; i <= sqrt(num); i++)//从start+1开始循环,循环到sqrt(num)
	{
		if (f(num - i * i, i))return true;//当发现一种情况满足条件时,返回true,不再循环。
	}
	return false;
}

递归函数f(int sum,int start)。num是当前数字,起始时为正整数m。start起始时为0。
写一个for循环,从start+1开始循环到sqrt(num).判断f(num-i*i,i)是否符合条件
num==0,表明这些不同数字的平方和正好等于num,return true
num<0,表明这些不同数字的平方和已经超出了num,return false
实际代码中for循环应放在两个if判断后面
别忘了最后return false(i循环到sqrt(num)时,num如果仍然大于0,以上条件均不满足)

为什么i循环到sqrt(num)?互不相同整数的平方和,不相同整数最多时,满足i(i+1)(2*i+1)/6=m即可(平方和公式)

不相同整数最少时(1个),就是sqrt(num)。这个数字是满足把m表示成互不相同整数的平方和的最大整数。

文章标题:【题解】平方和
文章链接:https://intmain0.com/38/
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。转载请注明出处
评论和私信会在第一时间回复。如果您觉得文章对您有帮助,可以点击文章右下角【分享】一下。您的鼓励是博主的最大动力!
暂无评论

发送评论 编辑评论


|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇