当前位置: 首页 > news >正文

杨辉三角形 (蓝桥杯) JAVA

目录

  • 题目描述:
  • 暴力破解(四成):
  • 二分法破解(满分):

题目描述:


下面的图形是著名的杨辉三角形:

在这里插入图片描述

如果我们按从上到下、从左到右的顺序把所有数排成一列,可以得到如下数列:

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, ...

给定一个正整数 N,请你输出数列中第一次出现 N 是在第几个数?

输入格式:

输入一个整数 N。

输出格式:

输出一个整数代表答案。

数据范围:

对于 20% 的评测用例,
1≤N≤10;
对于所有评测用例,1≤N≤10^9。

输入样例:

6

输出样例:

13


暴力破解(四成):

解题思路:

解决本难题的话,如果不是很了解杨辉三角的规律的话,可以用暴力混分。
想要暴力混分,得先明白杨辉三角形的最基本规的律:

1
1 1
1 2 1
1 3 3 1
1 2 6 4 1

1.每行首尾都是1
2.每行数字左右对称
3.第n行的数字有n列
4.每列上的元素值 = 上一行当前列元素值 + 上一行上一列元素值

了解上述基本规律就能将杨辉三角存入二维数组中,再输出。

对于本题我采用的是一维滚动数组来更新杨辉三角的值,因为一维数组最大可以分配 大概1 * 10^9左右的空间,能打印杨辉三角的最大宽度就很大了。而二维数组分配 10000*10000的空间就爆炸了。能打印杨辉三角的最大宽度就缩短了。

值得注意的是,更新一维数组的时候要从后往前更新,由于杨辉三角是具有对称性,所以不影响(从前往后更新的话,数据会被覆盖)。

用一维数组打印杨辉三角的代码如下:

import java.util.*;public class Main{public static long n = 0;public static void main(String[] args){long a[] = new long[1000000 + 1];for(int i = 0; i <= 10; i ++) {for(int j = i; j >= 0; j --) {if(j == 0 || i == j) {a[j] = 1L;System.out.print(a[j] + " ");continue;}a[j] = a[j] + a[j - 1];System.out.print(a[j] + " ");}System.out.println();}  }
}

用暴力破解本题,代码如下:

import java.util.*;public class Main{public static long n = 0;public static void main(String[] args){Scanner sc = new Scanner(System.in);n = sc.nextLong();long a[] = new long[1000000 + 1];long sum = 0;out : for(int i = 0; i <= 1000000; i ++) {for(int j = i; j >= 0; j --) {if(j == 0 || i == j) a[j] = 1L;else a[j] = a[j] + a[j - 1];if(a[j] == n) {sum ++;System.out.println(sum);break out;}sum ++;}}}
}

上代码在官方平台能拿四成分数,虽然不多,但如果只会暴力的话这么些代码,得这些分也是可以接受的:
在这里插入图片描述


二分法破解(满分):

思路:

要使用二分法破解本题,就要对杨辉三角形,每个位置上的元素规律都有进一步的了解。

下面直接给出结论:
在这里插入图片描述
上图可知,左边与右边对称,所以只需要研究左边即可。
在这里插入图片描述
上述的一半可以直接用下方的排列组合式子表示:
在这里插入图片描述
加一些标注如下图:
在这里插入图片描述
注意要求找到n第一次出现的位置:
很容易可以看到每一层 斜排 内的元素从上往下都是单调递增的,且越靠内扩张越快。所以靠内斜排 上的元素扩张的最快,所以能最快碰到第一个n。所以在二分查找的时候我们从内层外层 找(这样找到的 n 就是第一次出现的),由于杨辉三角扩散速度很快,所以 16 斜层 就可以包含10^9的数据。

如上图标记,我们从内往外,先 找 1 层,看是否有一个 C(r , k) = n 如果有的话我们直接退出,否者继续去找 2 层…直到找到一个C(r, k) = n 再通过r, k 找到这个数是第几次出现的(用N表示)。

这里直接给出结论:N = r *(r + 1) + k + 1
(上述公式只要知道:r, k 是从 0 开示的就不难推出N)

还需要注意的是本题用long变量储存数据,出现 long >> 1 + int 类型的式子是很容易让最终结果出错的。

例如:

public class text {public static void main(String[] args) {long a = 2L;System.out.print(a >> 1 + 1);}
}

输出:
在这里插入图片描述
修改方法有两种,正确代码:

public class text {public static void main(String[] args) {long a = 2L;long b = 1L;System.out.println((long)(a >> 1) + 1L);System.out.print(a / 2 + 1);}
}

输出:

在这里插入图片描述
理论成立本题完整代码如下:

import java.util.*;public class Main{public static int n = 0;public static void main(String[] args){Scanner sc = new Scanner(System.in);n = sc.nextInt();//别写成int nfor(int i = 16; i >= 0; i --) if(check(i)) break;
}	  public static long C(long a, long b) {//求排列组合C(a,b)的值long res = 1;//不要写成res = 0;for(long i = a, j = 1; j <= b; j ++, i --) {res = res * i / j;if(res > n) return res;//大于n直接退出防止爆long}return res;}public static boolean check(int k) {long L = 2 * k;//C(2*k, k) ~ C(N, k),这个区间内寻找一个C(r, k) = nlong R = n;//左右边界,C(1, n) = n,所以右边界最多是n while(L <= R) {long middle = (L + R) >> 1;//高效 除 2long nt = C(middle, k);if(nt > n) R = middle - 1;//大于查左边部分else if(nt < n) L = middle + 1;else {System.out.print((middle *(middle + 1)) / 2 + k + 1);//输出结果,再退出return true;} 	 }return false;}
}

在这里插入图片描述

相关文章:

杨辉三角形 (蓝桥杯) JAVA

目录题目描述&#xff1a;暴力破解&#xff08;四成&#xff09;&#xff1a;二分法破解&#xff08;满分&#xff09;&#xff1a;题目描述&#xff1a; 下面的图形是著名的杨辉三角形&#xff1a; 如果我们按从上到下、从左到右的顺序把所有数排成一列&#xff0c;可以得到如…...

AI制药 - AlphaFold Multimer 的 MSA Pairing 源码

目前最新版本是v2.3.1&#xff0c;2023.1.12 AlphaFold multimer v1 于 2021 年 7 月发布&#xff0c;同时发表了一篇描述其方法和结果的论文。AlphaFold multimer v1 使用了与 AlphaFold 单体相同的模型结构和训练方法&#xff0c;但增加了一些特征和损失函数来处理多条链。Al…...

TitanIDE:云原生开发到底强在哪里?

原文作者&#xff1a;行云创新技术总监 邓冰寒 引言 是一种新的软件开发方法&#xff0c;旨在构建更可靠、高效、弹性、安全和可扩展的应用程序。与传统的应用程序开发方式不同&#xff0c;云原生是将开发环境完全搬到云端&#xff0c;构建一站式的云原生开发环境。云原生的开…...

单片机常用完整性校验算法

一、前言 单片机在开发过程中经常会遇到大文件传输&#xff0c;或者大量数据传输&#xff0c;在一些工业环境下&#xff0c;数据传输并不是很稳定&#xff0c;如何检验数据的完整性就是个问题&#xff0c;这里简单介绍一下单片机常用的几种数据完整性校验方法。 二、CheckSum校…...

Anaconda 的安装配置及依赖项的内外网配置

在分享anaconda 的安装配置及使用前&#xff0c;我们必须先明白anaconda是什么&#xff1b;Anaconda是一个开源的Python发行版本。两者区别在于前者是一门编程语言&#xff0c;后者相当于编程语言中的工具包。 由于python自身缺少numpy、matplotlib、scipy、scikit-learn等一系…...

p84 CTF夺旗-PHP弱类型异或取反序列化RCE

数据来源 文章参考 本课重点&#xff1a; 案例1&#xff1a;PHP-相关总结知识点-后期复现案例2&#xff1a;PHP-弱类型对比绕过测试-常考点案例3&#xff1a;PHP-正则preg_match绕过-常考点案例4&#xff1a;PHP-命令执行RCE变异绕过-常考点案例5&#xff1a;PHP-反序列化考题…...

2022财报逆转,有赞穿透迷雾实现突破

2022年&#xff0c;商家经营面临困难。但在一些第三方服务商的帮助下&#xff0c;也有商家取得了逆势增长。 2023年3月23日&#xff0c;有赞发布2022年业绩报告&#xff0c;它帮助许多商家稳住了一整年的经营。2022年&#xff0c;有赞门店SaaS业务的GMV达到425亿元&#xff0c…...

蓝桥杯 - 求组合数【C(a,b)】+ 卡特兰数

文章目录&#x1f4ac;前言885. 求组合数 I C(m,n) 【dp】886 求组合数 II 【数据大小10万级别】 【费马小定理快速幂逆元】887. 求组合数 III 【le18级别】 【卢卡斯定理 逆元 快速幂 】888.求组合数 IV 【没有%p -- 高精度算出准确结果】 【分解质因数 高精度乘法 --只用一…...

膳食真菌在癌症免疫治疗中的作用: 从肠道微生物群的角度

谷禾健康 癌症是一种恶性肿瘤&#xff0c;它可以发生在人体的任何部位&#xff0c;包括肺、乳房、结肠、胃、肝、宫颈等。根据世界卫生组织的数据&#xff0c;全球每年有超过1800万人被诊断出患有癌症&#xff0c;其中约有1000万人死于癌症。癌症已成为全球范围内的主要健康问题…...

怎么将模糊的照片变清晰

怎么将模糊的照片变清晰?珍贵的照片每个人都会有&#xff0c;而遇到珍贵的照片变模糊了&#xff0c;相信会让人很苦恼的。那么有没有办法可以解决呢?答案是有的&#xff0c;我们可以用工具让模糊的照片变得清晰。下面就来分享一些让模糊的照片变清晰的方法&#xff0c;有兴趣…...

【软件测试】基础知识第一篇

文章目录一. 什么是软件测试二. 测试和调试的区别三. 什么是测试用例四. 软件的生命周期五. 软件测试的生命周期一. 什么是软件测试 软件测试就是验证软件产品特性是否满足用户的需求。 那需求又是什么呢&#xff1f;在多数软件公司&#xff0c;会有两种需求&#xff0c;一种…...

【百面成神】java web基础7问,你能坚持到第几问

前 言 &#x1f349; 作者简介&#xff1a;半旧518&#xff0c;长跑型选手&#xff0c;立志坚持写10年博客&#xff0c;专注于java后端 ☕专栏简介&#xff1a;纯手打总结面试题&#xff0c;自用备用 &#x1f330; 文章简介&#xff1a;java web最基础、重要的8道面试题 文章目…...

Centos7安装、各种环境配置和常见bug解决方案,保姆级教程(更新中)

文章目录前言一、Centos7安装二、各种环境配置与安装2.1 安装net-tools&#xff08;建议&#xff09;2.2 配置静态网络&#xff08;建议&#xff09;2.1 修改Centos7的时间&#xff08;建议&#xff09;2.2 Centos7系统编码问题2.3 vim安装&#xff08;建议&#xff09;2.4 解决…...

【C++进阶】智能指针

文章目录为什么需要智能指针&#xff1f;内存泄漏什么是内存泄漏&#xff0c;内存泄漏的危害内存泄漏分类&#xff08;了解&#xff09;如何避免内存泄漏智能指针的使用及原理smart_ptrauto_ptrunique_ptrshared_ptr线程安全的解决循环引用weak_ptr删除器为什么需要智能指针&am…...

软件测试面试题 —— 整理与解析(3)

&#x1f60f;作者简介&#xff1a;博主是一位测试管理者&#xff0c;同时也是一名对外企业兼职讲师。 &#x1f4e1;主页地址&#xff1a;&#x1f30e;【Austin_zhai】&#x1f30f; &#x1f646;目的与景愿&#xff1a;旨在于能帮助更多的测试行业人员提升软硬技能&#xf…...

springboot常用的20个注解

Spring Boot方式的项目开发已经逐步成为Java应用开发领域的主流框架&#xff0c;它不仅可以方便地创建生产级的Spring应用程序&#xff0c;还能轻松地通过一些注解配置与目前比较火热的微服务框架SpringCloud集成&#xff0c; 而Spring Boot 之所以能够轻松地实现应的创建及与…...

USB组合设备——带鼠标功能的键盘

文章目录带鼠标功能的键盘一个接口实现报告描述符示例多个接口实现复合设备和组合设备配置描述符集合的实现报告的返回附 STM32 枚举日志复合设备&#xff1a;Compound Device 内嵌 Hub 和多个 Function&#xff0c;每个 Function 都相当于一个独立的 USB 外设&#xff0c;有自…...

数据结构与算法基础-学习-18-哈夫曼编码

一、个人理解在远程通讯中&#xff0c;需要把字符转成二进制的字符串进行传输&#xff0c;例如我们需要传输ABCD&#xff0c;我们可以用定长的字符串进行表示&#xff0c;例如:A:00B:01C:02D:03这样可能就造成空间的浪费&#xff0c;我们多存储了一个0号位。那用变长呢&#xf…...

ZMC408CE | 实现“8通道独立PSO”应用场景

一、ZMC408SCAN产品亮点 1.高性能处理器&#xff0c;提升运算速度、响应时间和扫描周期等&#xff1b; 2.一维/二维/三维、多通道视觉飞拍&#xff0c;高速高精&#xff1b; 3.位置同步输出PSO&#xff0c;连续轨迹加工中对精密点胶胶量控制和激光能量控制等&#xff1b; 4…...

QuickJS中JS_SetClassProto方法把JavaScript对象指定为某个类的原型对象

在 QuickJS 中&#xff0c;JS_SetClassProto 方法用于设置一个类的原型对象。这个方法的作用是将一个 JavaScript 对象指定为该类的原型对象&#xff0c;从而定义该类的属性和方法。 具体来说&#xff0c;JS_SetClassProto 方法的第一个参数是指向 QuickJS 引擎执行上下文的指…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

莫兰迪高级灰总结计划简约商务通用PPT模版

莫兰迪高级灰总结计划简约商务通用PPT模版&#xff0c;莫兰迪调色板清新简约工作汇报PPT模版&#xff0c;莫兰迪时尚风极简设计PPT模版&#xff0c;大学生毕业论文答辩PPT模版&#xff0c;莫兰迪配色总结计划简约商务通用PPT模版&#xff0c;莫兰迪商务汇报PPT模版&#xff0c;…...

接口自动化测试:HttpRunner基础

相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具&#xff0c;支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议&#xff0c;涵盖接口测试、性能测试、数字体验监测等测试类型…...

Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)

引言 在人工智能飞速发展的今天&#xff0c;大语言模型&#xff08;Large Language Models, LLMs&#xff09;已成为技术领域的焦点。从智能写作到代码生成&#xff0c;LLM 的应用场景不断扩展&#xff0c;深刻改变了我们的工作和生活方式。然而&#xff0c;理解这些模型的内部…...

解读《网络安全法》最新修订,把握网络安全新趋势

《网络安全法》自2017年施行以来&#xff0c;在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂&#xff0c;网络攻击、数据泄露等事件频发&#xff0c;现行法律已难以完全适应新的风险挑战。 2025年3月28日&#xff0c;国家网信办会同相关部门起草了《网络安全…...

深度学习之模型压缩三驾马车:模型剪枝、模型量化、知识蒸馏

一、引言 在深度学习中&#xff0c;我们训练出的神经网络往往非常庞大&#xff08;比如像 ResNet、YOLOv8、Vision Transformer&#xff09;&#xff0c;虽然精度很高&#xff0c;但“太重”了&#xff0c;运行起来很慢&#xff0c;占用内存大&#xff0c;不适合部署到手机、摄…...