PTA L1-009 N个数求和 【C++】【辗转相除法】【Python】

C++:

辗转相除法

每次算最小公倍数和最大公约数都是用的常规思路,本身是不会有错的,但是当数据很大时,就会出现错误,时间复杂度过高

辗转相除法,又称欧几里德算法(Euclidean Algorithm),是求两个数的最大公约数(greatest common divisor)的一种方法。用较大的数除以较小的数,再以除数和余数反复做除法运算,当余数为0时,取当前算式除数为最大公约数

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

例:求38与18的最大公约数

30 / 18 = 1 余 12

18 / 12 = 1 余 6

12 /   6 = 2 余 0

当a<b时其实也是一样的,只不过多了一步

18 / 30 = 0 余 18

30 / 18 = 1 余 12

18 / 12 = 1 余 6

12 /   6 = 2 余 0

格式化输入:

一开始尝试了很多方法,包括头文件,转换成流,分割字符串,但是都很复杂,因为涉及到字符串到字符到整型的转换

本题的输入有两种简单巧妙的方法:

1.采用string里的getchar()略过每个数后面的字符(斜杠或者空格)

int N;
    cin>>N;
    int number[N*2];
    for(int i=0; i<N*2; i++){
    	cin>>number[i];
    	getchar();
	}

2.cin.ignore()忽视两个整数之间的斜杠,而cin是不会读入空格的

for (int i = 0; i < N; i++) 
	{
        cin >> numerators[i];
        cin.ignore(); // 忽略分数中的斜杠
        cin >> denominators[i];
    }

注意点:

测试点三主要是考察边界,当数字很大时的情况,有两种可能是通过不了测试的

1.先全部通分相加,再约分(数据溢出)

2.没有使用long long int型

输出时注意分类讨论

本题代码

#include <iostream>
#include <vector>

using namespace std;

// 返回两个数的最大公约数
long long int gcd(long long int a,long long  int b) {
    return b == 0 ? a : gcd(b, a % b);
}

// 返回两个数的最小公倍数
long long int lcm(long long int a,long long int b) {
    return a * b / gcd(a, b);
}
/* 
//注释掉的为常规思路,但是当数字很大时,时间复杂度过高 
// 返回两个数的最大公约数
long long int gcd(long long int a,long long  int b) {
    int k=1;
    for(int i=2;i<=(a<b?a:b);i++){
        while(a%i==0 && b%i==0){
            a/=i;
            b/=i;
            k*=i;
        }//注意是循环不是判断
    }
    return k; 
}

// 返回两个数的最小公倍数
long long int lcm(long long int a,long long int b) {
    return a*b/gcd(a,b);
}
*/ 
int main() {
    int N;
    cin >> N;
    if(N==0)
    {
    	cout<<0;
    	return 0;
	}
	//两个动态数组 
    vector<int> numerators(N), denominators(N);
	//格式化读入数据 
    for (int i = 0; i < N; i++) 
	{
        cin >> numerators[i];
        cin.ignore(); // 忽略分数中的斜杠
        cin >> denominators[i];
    }

    // 初始化和的分子和分母为第一个分数
    long long int sum_numerator = numerators[0];
    long long int sum_denominator = denominators[0];

    for (int i = 1; i < N; i++) 
	{
        // 通分
        long long int common_denominator = lcm(sum_denominator, denominators[i]);
        sum_numerator = sum_numerator * (common_denominator / sum_denominator) + numerators[i] * (common_denominator / denominators[i]);
        sum_denominator = common_denominator;
        
        // 约分
        long long int common_factor = gcd(sum_numerator, sum_denominator);
        sum_numerator /= common_factor;
        sum_denominator /= common_factor;
    }

    // 输出结果分类讨论 
    if (sum_denominator == 1 || sum_numerator == 0) 
	{
        cout << sum_numerator;
    } 
	else 
	{
    	//提出整数部分,使分子小于分母 
    	if(sum_numerator/sum_denominator!=0)
    	{ 
    		cout<<sum_numerator/sum_denominator<<' ';
    	} 
    	sum_numerator %= sum_denominator;
    	if(sum_numerator)
    	{ 
        	cout << sum_numerator << '/' << sum_denominator;
        } 
    }
    return 0;
}

Python:

注意点:

1.split分割字符串默认得到列表,所以要转换为整型

2.计算默认为浮点型,输出也要转换

# n个数相加
# 输入
# 5
# 2/5 4/15 1/30 -2/60 8/3
# 输出
# 3 1/3

# 最大公约数
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


# 最小公倍数
def lcm(a, b):
    return a * b / gcd(a, b)


N = int(input())
lst = list(map(str,input().split(' ')))
# ['2/5', '4/15', '1/30', '-2/60', '8/3']
lst2=[]
for i in lst:
    lst2.append(i.split('/'))  # ['2', '5']
sum_a, sum_b = int(lst2[0][0]), int(lst2[0][1])
for i in range(1, N):
    # 通分
    b_common = lcm(sum_b, int(lst2[i][1]))
    sum_a = sum_a * (b_common / sum_b) + int(lst2[i][0]) * (b_common / int(lst2[i][1]))
    sum_b = b_common
    # 约分
    the_common = gcd(sum_a, sum_b)
    sum_a /= the_common
    sum_b /= the_common
if sum_a == 0 or sum_b == 1:
    print(int(sum_a))
else:
    if sum_a // sum_b > 0:
        print(int(sum_a // sum_b),end=' ')
        sum_a = sum_a % sum_b
    if sum_a != 0:
        print(f"{int(sum_a)}/{int(sum_b)}")

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/555931.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

接口压力测试 jmeter--增强篇(二)

前期准备 1. JMeter的插件的安装 下载Jmeter Plugins Manager对插件进行管理 &#xff08;1&#xff09;下载地址&#xff1a;https://jmeter-plugins.org/install/Install/ &#xff08;2&#xff09;下载后&#xff0c;将jar包放到jmeter包目录下/lib/ext目录下 &#xff0…

【YOLOv8改进[检测头Head]】YOLOv8的“新头”之动态头(DynamicHead)

目录 一 DynamicHead 二 YOLOv8的“新头”之动态头 1 总体修改 2 配置文件 3 训练 其他 一 DynamicHead 官方论文地址&#xff1a;https://arxiv.org/pdf/2106.08322.pdf 官方代码地址&#xff1a;GitCode - 开发者的代码家园 在计算机视觉应用中&#xff0c;目标检测…

启动appium服务的2种方法(python脚本cmd窗口)

1.通过cmd窗口命令来启动 2.通过python代码启动 2.1启动单个appium服务 2.2启动多个appium服务 3.端口说明 一.端口号设置Appium服务器端口&#xff1a;4723 bp端口&#xff1a;4724 Appium服务器端口&#xff1a;4725 bp端口&#xff1a;4726可以看到appium服务器端口和bp端…

SpringBoot(一)【入门】

前言 1、SpringBoot 快速入门 1.1、SpringBoot 简介 SpringBoot 是用来简化 Spring 应用的初始搭建以及开发过程 首先我们回顾一下 SpringMVC 项目的开发过程&#xff1a; 导入依赖&#xff08;javax.servlet-api 和 spring-webmvc&#xff09;Servlet 容器配置类&#xff…

VirtualBox虚拟机使用win11系统,忘记密码如何重置密码

1. 点击重启同时按住Shift&#xff08;按住不放&#xff09; 2. 直到出现下面的界面&#xff0c;释放Shift&#xff0c;并进入疑难解答 3. 进入高级选项 4. 进入命令提示符 5. 发现当前是在X盘&#xff1f; 6. 进入C:\Windows\System32 c: cd Windows\System32 7. 备份osk.exe…

SpringCloud系列(5)--SpringCloud微服务工程公共部分提取

前言&#xff1a;在上一章节中我们创建了两个个SpringCloud工程&#xff0c;但在两个工程中分别存在着一些重复的部分&#xff0c;例如重复的实体类&#xff08;如图所示&#xff09;&#xff0c;这样会造成系统的冗余&#xff0c;所以我们需要把公共的类提取到一个工程里&…

预约小程序新选择:强大后端管理功能一览

拥有一个功能齐全、操作便捷的小程序对于商家来说至关重要。为了满足广大商家的需求&#xff0c;乔拓云平台提供了丰富的模板资源&#xff0c;帮助用户快速搭建预约型小程序&#xff0c;并配备了强大的后端管理功能&#xff0c;让商家能够轻松管理预约订单&#xff0c;提升运营…

Centos7 ElasticSearch集群搭建

1. 服务器环境配置 1.1 配置hosts文件 3台服务器都要执行 vim /etc/hosts; # 将以下内容写入3台服务器hosts文件 192.168.226.148 es001 192.168.226.149 es002 192.168.226.150 es003 1.2 关闭防火墙 3台服务器都要执行 systemctl stop firewalld; systemctl disable…

【opencv】dnn示例-speech_recognition.cpp 使用DNN模块结合音频信号处理技术实现的英文语音识别...

模型下载地址&#xff1a; https://drive.google.com/drive/folders/1wLtxyao4ItAg8tt4Sb63zt6qXzhcQoR6 终端输出&#xff1a;&#xff08;audio6.mp3 、audio10.mp3&#xff09; [ERROR:00.002] global cap_ffmpeg_impl.hpp:1112 open VIDEOIO/FFMPEG: unsupported parameter…

# 从浅入深 学习 SpringCloud 微服务架构(一)基础知识

从浅入深 学习 SpringCloud 微服务架构&#xff08;一&#xff09;基础知识 1、系统架构演变&#xff1a; 1&#xff09;单体应用架构。如电商项目。 用户管理、商品管理、订单管理&#xff0c;在一个模块里。 优点&#xff1a;开发简单&#xff0c;快速&#xff0c;适用于…

Mac下brew安装php7.4

这里作者挂了梯子&#xff0c;所以很流畅&#xff01; brew的下载&#xff0c;可参考另外一篇博文&#xff5e;Homebrew 安装与卸载 1、将第三方仓库加入brew brew tap shivammathur/php2、安装指定版本的PHP brew install php7.43、替换Mac自带PHP环境并刷新环境变量 -> …

基于simulink的模拟锁相环和数字锁相环建模与对比仿真

目录 1.课题概述 2.系统仿真结果 3.核心程序与模型 4.系统原理简介 4.1 模拟锁相环&#xff08;PLL&#xff09;的基本原理 4.2 数字锁相环&#xff08;DPLL&#xff09;的基本原理 5.完整工程文件 1.课题概述 模拟锁相环和数字锁相环建模的simulink建模&#xff0c;对…

OpenHarmony UI动画-recyclerview_animators

简介 带有添加删除动画效果以及整体动画效果的list组件库 下载安装 ohpm install ohos/recyclerview-animatorsOpenHarmony ohpm 环境配置等更多内容&#xff0c;请参考如何安装OpenHarmony ohpm 包 使用说明 引入组件库 import { RecyclerView } from "ohos/recycler…

Qt/C++音视频开发70-无感切换通道/无缝切换播放视频/多通道流畅切换/不同视频打开无缝切换

一、前言 之前就写过这个方案&#xff0c;当时做的是ffmpeg内核版本&#xff0c;由于ffmpeg内核解析都是代码实现&#xff0c;所以无缝切换非常完美&#xff0c;看不到丝毫的中间切换过程&#xff0c;看起来就像是在一个通道画面中。其实这种切换只能说是取巧办法&#xff0c;…

排序算法之计数排序

目录 一、简介二、代码实现三、应用场景 一、简介 算法平均时间复杂度最好时间复杂度最坏时间复杂度空间复杂度排序方式稳定性计数排序O(nk )O(nk)O(nk)O(k)Out-place稳定 稳定&#xff1a;如果A原本在B前面&#xff0c;而AB&#xff0c;排序之后A仍然在B的前面&#xff1b; 不…

稀碎从零算法笔记Day52-LeetCode:从双倍数组中还原原数组

题型&#xff1a;数组、贪心 链接&#xff1a;2007. 从双倍数组中还原原数组 - 力扣&#xff08;LeetCode&#xff09; 来源&#xff1a;LeetCode 题目描述 一个整数数组 original 可以转变成一个 双倍 数组 changed &#xff0c;转变方式为将 original 中每个元素 值乘以 …

记录ubuntu20.04安装nvidia-525.85.05显卡驱动(学习笔记2024.4.15、4.16)

电脑&#xff1a;华硕天选X2024 显卡&#xff1a;4060Ti i5-14400F 架构&#xff1a;x86_64 我需要使用Linux系统使用IsaacSim进行仿真&#xff0c;所以安装的都是IsaacSim中的推荐版本。 一.对新鲜的电脑进行分盘 电脑刚到手&#xff0c;900多个G全在C盘里&#xff0c;给它…

学习笔记(4月18日)vector底层模拟实现(1)

1.迭代器 vector实际上是由迭代器进行维护的&#xff0c;关于迭代器是什么&#xff0c;为什么要叫这个名字&#xff0c;后面的学习会逐渐了解&#xff0c;现在先将迭代器是作为指针即可。 vector底层有三个迭代器&#xff0c;用来起到容量、数组头、元素个数的作用。 同时为…

数字零售力航母-看微软如何重塑媒体

数字零售力航母-看微软如何重塑媒体 - 从2024全美广播协会展会看微软如何整合营销媒体AI技术和AI平台公司 2024年&#xff0c;微软公司联合英伟达总司&#xff0c;赞助全美广播协会展会。本次展会微软通过搭建一个由全面的合作伙伴生态系统支持的可信和安全的平台&#xff0c;…

RIP最短路实验(华为)

思科设备参考&#xff1a;RIP最短路实验&#xff08;思科&#xff09; 一&#xff0c;技术简介 RIP&#xff08;Routing Information Protocol&#xff0c;路由信息协议&#xff09;是一种基于距离矢量的内部网关协议&#xff0c;工作原理是每个路由器周期性地向邻居路由器发…