母函数法解决整数划分
解决 函数 整数 划分
2023-09-11 14:20:42 时间
问题描写叙述:把一个整数n划分成1到n的划分,比如3能够划分为1+1+1,1+2,3这三种划分。那么求n的划分数。
解题思路:
能够把1,设为x的0次方:x^0
把1,设为x的1次方:x^1
.......把n。设为是x的n次方:x^n
那么1可能出现。0,1,2,3,4,5,6...n次,而2可能出现0,1,2,3,.......n/2次,3可能出现0,1,2,3,4........n/3次等等。
按照上面的把1能够表示成x^1:那么可能出现的次数就是1+x^1+2*x^1+3*x^1+...n*x^1,同理有1+1*x^2+2*x^2+.....(n/2)*x^2那么把这些多项式相乘起来,得
(1+1*x^1+2*x^1....n*x^1)(1+x^2+2*x^2....(n/2)*x^2).....(x^n)是不是x^n终于的系数就是n的整数划分数,以下是我的代码:
public class Main { public static int getNum(int n){ //存放终于的结果 int[] c1=new int[n+1]; //存放当前两个多项式相乘的结果 int[] c2=new int[n+1]; //初始化让c1開始的系数全为1 Arrays.fill(c1, 1); //初始化让c2開始的系数全为0 Arrays.fill(c2, 0); for(int i=2;i<=n;i++){ //i代表当前的x究竟是多少次方 for(int j=0;j<n+1;j++){ //j代表从c1取出每一个系数准备与当前多项式相乘 for(int k=0;k+j<=n;k+=i){ //k代表从当前x次方的多项式取出每一项然后,与c1里的多项式相乘 c2[j+k]+=c1[j]; } } //将c2存储的缓存结果放入c1 for(int z=0;z<n+1;z++){ c1[z]=c2[z]; c2[z]=0; } } return c1[n]; } public static void main(String[] args) { System.out.println(getNum(100)); } }
相关文章
- 一次永久解决cmd窗口汉字显示乱码
- 如何解决C#异常:必须先将当前线程设置为单线程单元(STA)模式,然后才能进行OLE调用,请确保你的Main函数已在其上标记了STAThreadAttribute
- 开发函数计算的正确姿势——轻松解决大依赖部署
- 【COCOS2DX-LUA 脚本开发之十一】C/C++与LUA之间进行数据函数交互以及解决“PANIC: UNPROTECTED ERROR IN CALL TO LUA API (ATTEMPT TO INDEX A NIL VALUE)”的问题
- 服务器返回的“未在本地计算机上注册“Microsoft.ACE.OLEDB.12.0提供程序””错误解决
- Atitit 解决Unhandled event loop exception错误的办法
- atitit.解决struts2 SpringObjectFactory.getClassInstance NullPointerException v2 q31
- 成功解决AttributeError: module ‘tensorflow‘ has no attribute ‘contrib‘
- 成功解决r2_score函数输出值始终为0的情况
- Linux异步信号处理函数引发的死锁及解决方法
- 成功解决基于model利用plot_importance()函数出现仅输出一个、两个或者三个等特征(极少的特征)
- 成功解决利用pandas的read_csv函数读取csv文件的时候出现中文乱码问题
- 成功解决ERROR: Could not install packages due to an EnvironmentError: [Errno 28] No space left on device
- 【解决if else】还在用策略模式解决 if-else?Map+函数式接口方法才是YYDS!
- 已解决HTTPConnectionPool(host=‘117.89.172.166‘, port=31265): Max retries exceeded with url: http://data
- 已解决pandas.apply函数使用方法
- 如何在直播中解决黑屏、花屏、闪屏问题 | 直播疑难杂症排查
- 4种方法帮你解决IntelliJ IDEA控制台中文乱码问题
- qtcpsocket调用write和read函数写数据乱码问题解决方法
- 解决gvim中php函数提示php_funclist.dict无法生效的问题
- Linux系统shell脚本实战之解决生产ddos攻击
- 关于log_bin_trust_function_creators导致的函数不能执行的解决(问题记录)
- 完美解决在Windows下Vs Code编译不同C函数之间的调用问题
- 解决:无法将“Add-Migration”项识别为 cmdlet、函数、脚本文件或可运行程序的名称。请检查名称的拼写,如果包括路径,请确保路径正确,然后再试一次
- 远程服务器证书过期怎么解决,关于演示win7远程桌面证书过期的具体操作方式...