暴力+輾轉相除法——N個數求和

来源:https://www.cnblogs.com/Louise-Zhou/archive/2020/03/24/Louise_Z.html
-Advertisement-
Play Games

從題目“分子/分母”的輸入形式可以看出我們不能採用scanf和cin直接輸輸入值 而要採用字元輸入再轉換為數值 計算過程中判斷好符號 暴力通分直接加減即可 防止通分過程超出長整型範圍 最好每一步結果都約分 我最開始暴力約分來著 發現會超時 就用歐幾裡得演算法了 不麻煩也不會超時 輸出時註意題目... ...


題目來源

PTA 團體程式設計天梯賽-練習集 L1-009 N個數求和 (20分)

https://pintia.cn/problem-sets/994805046380707840/problems/994805133597065216

 

題目描述

本題的要求很簡單,就是求N個數字的和。麻煩的是,這些數字是以有理數分子/分母的形式給出的,你輸出的和也必須是有理數的形式。

輸入格式:

輸入第一行給出一個正整數N(≤100)。隨後一行按格式a1/b1 a2/b2 ...給出N個有理數。題目保證所有分子和分母都在長整型範圍內。另外,負數的符號一定出現在分子前面。

輸出格式:

輸出上述數字和的最簡形式 —— 即將結果寫成整數部分 分數部分,其中分數部分寫成分子/分母,要求分子小於分母,且它們沒有公因數。如果結果的整數部分為0,則只輸出分數部分。

樣例:

輸入樣例1:

5
2/5 4/15 1/30 -2/60 8/3

輸出樣例1:

3 1/3

輸入樣例2:

2
4/3 2/3

輸出樣例2:

2

輸入樣例3:

3
1/3 -1/6 1/8

輸出樣例3:

7/24

 

思路

從題目“分子/分母”的輸入形式可以看出我們不能採用scanf和cin直接輸輸入值 而要採用字元輸入再轉換為數值

計算過程中判斷好符號 暴力通分直接加減即可

防止通分過程超出長整型範圍 最好每一步結果都約分

我最開始暴力約分來著 發現會超時 就用歐幾裡得演算法了 不麻煩也不會超時

輸出時註意題目要求的形式 想仔細一點每種條件怎麼輸出即可

 

代碼

 1 #include <cstdio>
 2 using namespace std;
 3 int n,o=1,oo; char x=1; //o-結果是否為非負數 oo-當前輸入的有理數是否為非負數
 4 long long p,q,f=0,g=1,c;
 5 inline long long read(); //快讀 由於分子分母間有‘/’分隔且分母一定是正數 標準快讀模板即可完成
 6 inline int yue(long long a,long long b);//求a和b的最大公約數
 7 int main()
 8 {
 9   scanf("%d",&n); 
10   for(int i=1;i<=n;i++)
11   {
12     while(!(x>=48&&x<=57)&&x!='-')
13       x=getchar();
14     if(x=='-') oo=0;
15     else    oo=1; //判斷當前輸入的有理數是否為非負數
16     p=read();
17     q=read(); //以“|p/q|”形式讀入當前有理數
18     p*=g;
19     f*=q;
20     g*=q; //暴力通分 本題數據範圍內沒有超出長整型
21     if((o&&oo)||(!o&&!oo)) //如果結果和當前輸入有理數同號 只要分子絕對值部分相加即可
22       f+=p;
23     else if(o&&!oo) //如果結果為正 當前輸入有理數為負 則需要比較結果與當前輸入有理數的大小來確定此次運算後結果的符號 
24     {
25       if(f>=p) //當前結果大於當前輸入有理數的絕對值 結果仍為正數 以下同理 
26         f-=p;
27       else
28         o=0,f=p-f;
29     }
30     else if(!o&&oo)
31     {
32       if(f>=p)
33         o=1,f-=p;
34       else
35         f=p-f;
36     }
37     int u=yue(f,g); //u為f和g的最大公約數
38     f/=u;
39     g/=u; //約分
40   }
41   if(o==0) printf("-"); //如果結果是負數 輸出負號
42   if(f==0)    printf("0"); //如果結果是0 輸出0
43   else if(f%g==0)    printf("%lld",f/g); //如果結果可以約分為整數
44   else if(g%f==0) printf("1/%lld",g/f);//如果結果可以約分為“1/x”形式
45   else if(f>g) //如果結果的分子大於分母 即結果為假分數 需要轉化為帶分數
46   {
47     printf("%lld ",f/g); //整數部分
48     f%=g;
49     printf("%lld/%lld",f,g); //分數部分
50   }
51   else
52     printf("%lld/%lld",f,g); //如果結果為真分數
53   return 0;
54 }
55 inline int yue(long long a,long long b) //歐幾裡得演算法 親測暴力約分會超時
56 {
57   if(a>b) c=a,a=b,b=c; 
58   while(a!=0) //
59   {
60     while(b>=a) //標準%運算比較慢 直接減
61       b-=a;
62     c=a,a=b,b=c;
63   }
64   return b;
65 }
66 inline long long read()
67 {
68   long long s=0;
69   while(!(x>=48&&x<=57))
70     x=getchar();
71   while(x>=48&&x<=57)
72     s*=10,s+=x-48,x=getchar();
73   return s;
74 }

 

吐槽

很少見到PTA這樣AC紅WA綠的平臺了 屬實清新脫俗:)


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • E. Efficient Exchange 題意:這一題的題意簡單;簡單來說就是A、B有1元10元、100元、1000元。。。。等等10的整次冪的票額的紙幣,現在B付錢給A,問當中涉及錢的張數最少是多少可以把錢付清。 題解:這一題官方題解給的是DP+遞歸,自己看了半天,代碼中的註釋給出了自己的理解, ...
  • 1 簡介 項目越做越發覺得,任何一個系統上線,運維監控都太重要了。關於Springboot微服務的監控,之前寫過 "【Springboot】用Springboot Admin監控你的微服務應用" ,這個方案可以實時監控並提供告警提醒功能,但不能記錄歷史數據,無法查看過去1小時或過去1天等運維情況。本 ...
  • 一、對象類文件的序列換與反序列化 1.java.io.ObjectOutputStream;序列化JAVA對象到硬碟 2.java.io.ObjectInputStream;將硬碟中的數據“反序列化”到JVM記憶體中 Compile編譯(java->class) DeCompile反編譯(class- ...
  • 什麼場景該使用通用計價 如果商品的費用屬性一直在變化,比如隔三岔五的新增某種費用(按新規則計算的新費用),作為開發人員的你每次需要膽戰心驚的維護現有的計價介面,測試也需要花費大量時間驗證對其他費用的影響。基於這一點,我在想如果初期把計價做成一個通用的計價介面,每次加費用我只需要關註新費用的計算規則, ...
  • 繼承的優點:減少代碼的冗餘 提高代碼的重用性 派生類定義格式: Class 派生類名 : 繼承方式 基類名{ //派生類新增的數據成員和成員函數 }; class 子類: 繼承方式 父類名{ //子類新增的數據成員和成員函數 }; 繼承方式分類: public : 公有繼承 (重要) private ...
  • 什麼是defer? defer語句是專門在函數結束以後做一些清理工作的。我們先舉一個例子來更好的理解,現在有一個函數,它的作用是把一個文件內容拷貝到另一個文件。 以上代碼是可以正常執行的,但是存在一個問題,如果os.Create執行失敗,那麼就無法執行到文件資源的Close函數。進程每打開一個文件就 ...
  • Java中的匿名對象 1. 什麼是匿名對象? 所謂匿名對象就是沒有名稱的對象; 2. 匿名對象有哪些常見的用法? + 匿名對象可以作為實際參數傳遞給函數; + 可以直接通過匿名對象調用該對象的方法; 3. 匿名對象的具體使用方式 ...
  • 說明: 作為反射工具類,通過對象和屬性的名字獲取對象屬性的值,如果在當前對象屬性沒有找到,依次向上收集所有父類的屬 性,直到找到屬性值,沒有找到返回null; 代碼: 1.classUtil package com.example.demo.utill; import java.lang.refle ...
一周排行
    -Advertisement-
    Play Games
  • Timer是什麼 Timer 是一種用於創建定期粒度行為的機制。 與標準的 .NET System.Threading.Timer 類相似,Orleans 的 Timer 允許在一段時間後執行特定的操作,或者在特定的時間間隔內重覆執行操作。 它在分散式系統中具有重要作用,特別是在處理需要周期性執行的 ...
  • 前言 相信很多做WPF開發的小伙伴都遇到過表格類的需求,雖然現有的Grid控制項也能實現,但是使用起來的體驗感並不好,比如要實現一個Excel中的表格效果,估計你能想到的第一個方法就是套Border控制項,用這種方法你需要控制每個Border的邊框,並且在一堆Bordr中找到Grid.Row,Grid. ...
  • .NET C#程式啟動閃退,目錄導致的問題 這是第2次踩這個坑了,很小的編程細節,容易忽略,所以寫個博客,分享給大家。 1.第一次坑:是windows 系統把程式運行成服務,找不到配置文件,原因是以服務運行它的工作目錄是在C:\Windows\System32 2.本次坑:WPF桌面程式通過註冊表設 ...
  • 在分散式系統中,數據的持久化是至關重要的一環。 Orleans 7 引入了強大的持久化功能,使得在分散式環境下管理數據變得更加輕鬆和可靠。 本文將介紹什麼是 Orleans 7 的持久化,如何設置它以及相應的代碼示例。 什麼是 Orleans 7 的持久化? Orleans 7 的持久化是指將 Or ...
  • 前言 .NET Feature Management 是一個用於管理應用程式功能的庫,它可以幫助開發人員在應用程式中輕鬆地添加、移除和管理功能。使用 Feature Management,開發人員可以根據不同用戶、環境或其他條件來動態地控制應用程式中的功能。這使得開發人員可以更靈活地管理應用程式的功 ...
  • 在 WPF 應用程式中,拖放操作是實現用戶交互的重要組成部分。通過拖放操作,用戶可以輕鬆地將數據從一個位置移動到另一個位置,或者將控制項從一個容器移動到另一個容器。然而,WPF 中預設的拖放操作可能並不是那麼好用。為瞭解決這個問題,我們可以自定義一個 Panel 來實現更簡單的拖拽操作。 自定義 Pa ...
  • 在實際使用中,由於涉及到不同編程語言之間互相調用,導致C++ 中的OpenCV與C#中的OpenCvSharp 圖像數據在不同編程語言之間難以有效傳遞。在本文中我們將結合OpenCvSharp源碼實現原理,探究兩種數據之間的通信方式。 ...
  • 一、前言 這是一篇搭建許可權管理系統的系列文章。 隨著網路的發展,信息安全對應任何企業來說都越發的重要,而本系列文章將和大家一起一步一步搭建一個全新的許可權管理系統。 說明:由於搭建一個全新的項目過於繁瑣,所有作者將挑選核心代碼和核心思路進行分享。 二、技術選擇 三、開始設計 1、自主搭建vue前端和. ...
  • Csharper中的表達式樹 這節課來瞭解一下表示式樹是什麼? 在C#中,表達式樹是一種數據結構,它可以表示一些代碼塊,如Lambda表達式或查詢表達式。表達式樹使你能夠查看和操作數據,就像你可以查看和操作代碼一樣。它們通常用於創建動態查詢和解析表達式。 一、認識表達式樹 為什麼要這樣說?它和委托有 ...
  • 在使用Django等框架來操作MySQL時,實際上底層還是通過Python來操作的,首先需要安裝一個驅動程式,在Python3中,驅動程式有多種選擇,比如有pymysql以及mysqlclient等。使用pip命令安裝mysqlclient失敗應如何解決? 安裝的python版本說明 機器同時安裝了 ...