算法学习——递推之摆动数列
2023-02-18 16:39:50 时间
算法描述
已知递推数列:
a(1)=1
a(2i)=a(i)+1
a(2i+1)=a(i)+a(i+1) (i为正整数)
求该数列的第n项,以及前n项中的最大值为多少,其n为多少?
算法思路
-
采用递推的方法,使用一维数组,从2开始递推,一直递推到n
a(i)=a(i/2)+1(n为偶数)
a(i)=a((i+1)/2)+((i-1)/2) (n为奇数)
我们只需要使用一个是否被2整除来判断n是偶数还是奇数,从而选择相对应的递推公式
-
查找最大值也容易,设置一个变量,只需要遍历该数组,遇到比变量大的就把该数值赋值给该变量
-
最大值所对应的项可能不止一个,所以我们找到一个就把该项数(数组的下标)打印出来
算法实现
System.out.println("请输入n:");
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
scanner.close();
int[] a = new int[n+1];//从1开始,所以n+1
a[1]=1;//初始条件
//分条件进行正向递推
for(int i=2;i<=n;i++){
if(i%2==0){
a[i] = a[i/2]+1;
}else{
a[i] = a[(i+1)/2]+a[(i-1)/2];
}
}
System.out.println("a("+n+")为"+a[n]);
//遍历整个数组,找到最大值
int max = 0;
for(int i=1;i<=n;i++){
if(max<a[i]){
max = a[i];
}
}
//遍历数组,找到与最大值相等的数,将该下标(项数)打印出来
for(int i=1;i<=n;i++){
if(max==a[i]){
System.out.print("a("+i+")=");
}
}
System.out.print(max);
结果
相关文章
- ASP.NET
- 使用Commons Logging
- 记一次 .NET 某自动化采集软件 崩溃分析
- [C# 中的序列化与反序列化](.NET 源码学习)
- .NET 向量类型的运算结果范例——用于学习Vector类所提供百多个向量方法
- 树莓派(香橙派)通过.NET IoT 操作SPI编写屏幕驱动 顺手做个四足机器人(一)
- WPF自定义控件之消息提示
- .NET跨平台框架选择之一 - Avalonia UI
- 篇(16)-Asp.Net Core入门实战-权限管理之用户创建与关联角色(ViewModel再用与模型验证二)
- 学习ASP.NET Core Blazor编程系列十——路由(下)
- 代码生成器(CodeBuilder) 2.9.4 稳定版
- 篇(15)-入门实战-权限管理之用户创建与关联角色(ViewModel再用与模型验证一)
- 篇(14)-Asp.Net Core入门实战-权限管理之角色编辑和赋权(ViewModel-DTO初探)
- 算法-2 选择排序、冒泡排序、插入排序
- 篇(13)-Asp.Net Core入门实战-将功能代码增加异步功能Async和配置简单防范CSRF攻击
- NET 6 实现滑动验证码(一)、创建工程
- 算法-1 算法复杂度
- 在WPF中使用Prism弹出自定义窗体样式的对话框
- 使用Fody时,CS-SCRIPT动态代码无法找到程序集
- C# 使用SIMD向量类型加速浮点数组求和运算(3):循环展开