【Java版oj】day31美国节日、分解因数

冷不防 2024-03-24 17:43 2阅读 0赞

**目录**

一、美国节日

（1）原题再现

（2）问题分析

（3）完整代码

二、分解因数

（1）原题再现

（2）问题分析

（3）完整代码

三、DFS深度优先列举所有可能的情况

--------------------

> ## 一、美国节日 ##
> 
> ### （1）原题再现 ###
> 
> [美国节日\_\_牛客网][Link 1]
> 
> 和中国的节日不同，美国的节假日通常是选择某个月的第几个星期几这种形式，因此每一年的放假日期都不相同。具体规则如下：  
> \* 1月1日：元旦  
> \* 1月的第三个星期一：马丁·路德·金纪念日  
> \* 2月的第三个星期一：总统节  
> \* 5月的最后一个星期一：阵亡将士纪念日  
> \* 7月4日：美国国庆  
> \* 9月的第一个星期一：劳动节  
> \* 11月的第四个星期四：感恩节  
> \* 12月25日：圣诞节  
> 现在给出一个年份，请你帮忙生成当年节日的日期。
> 
> **输入描述**
> 
> 输入包含多组数据，每组数据包含一个正整数year（2000≤year≤9999）。
> 
> **输出描述**
> 
> 对应每一组数据，以“YYYY-MM-DD”格式输出当年所有的节日日期，每个日期占一行。
> 
> 每组数据之后输出一个空行作为分隔。
> 
> 示例
> 
> 输
> 
> 2014
> 
> 201
> 
> 输
> 
> 2014-01-01
> 
> 2014-01-20
> 
> 2014-02-17
> 
> 2014-05-26
> 
> 2014-07-04
> 
> 2014-09-01
> 
> 2014-11-27
> 
> 2014-12-25
> 
> 2013-01-01
> 
> 2013-01-21
> 
> 2013-02-18
> 
> 2013-05-27
> 
> 2013-07-04
> 
> 2013-09-02
> 
> 2013-11-28
> 
> 2013-12-25
> 
> ### （2）问题分析 ###
> 
> 根据蔡勒公式计算星期数。（以下摘自百度百科）
> 
> ![f1c70800112b44f798fb1282d2f1c7d0.png][]
> 
> （或者是：![29ef5bc8861a4d308fe1cd35ec1632ad.png][]
> 
> ）
> 
> 若要计算的日期是在1582年10月4日或之前，公式则为
> 
> ![d8d125a33dda41018444b5589d6aa367.png][]
> 
> 以1582年10月4日为例：
> 
> 1582年10月4日后：w = (d + 1+ 2\*m+3\*(m+1)/5+y+y/4-y/100+y/400)%7;
> 
> 1582年10月4日前：w = (d+1+2\*m+3\*(m+1)/5+y+y/4+5) % 7;
> 
> 或者1752年9月3日为例
> 
> 1752年9月3日后：w = (d + 2\*m+3\*(m+1)/5+y+y/4-y/100+y/400)%7;（这个公式应该是跟正常的相差1的，也就是算出来相差了一天）
> 
> 1752年9月3日前：w = (d+2\*m+3\*(m+1)/5+y+y/4+5) % 7;
> 
> 注：罗马教皇决定在1582年10月4日后使用格利戈里历法；而英国则是在1752年9月3日后才接受使用格利戈里历法。
> 
> 注意：
> 
> 当年的1,2月要当成上一年的13,14月进行计算
> 
> 符号意义：
> 
> **w**：星期； w对7取模得：0-星期日，1-星期一，2-星期二，3-星期三，4-星期四，5-星期五，6-星期六
> 
> **c**：世纪（注：一般情况下，在公式中取值为已经过的世纪数，也就是年份除以一百的结果，而非正在进行的世纪，也就是现在常用的年份除以一百加一；不过如果年份是公元前的年份且非整百数的话，c应该等于所在世纪的编号，如公元前253年，是公元前3世纪，c就等于-3）
> 
> **y**：年（一般情况下是后两位数，如果是公元前的年份且非整百数，y应该等于cMOD100+100）
> 
> **m**：月（m大于等于3，小于等于14，即在蔡勒公式中，某年的1、2月要看作上一年的13、14月来计算，比如2003年1月1日要看作2002年的13月1日来计算）
> 
> **d**：日
> 
> \[ \]代表取整，即只要整数部分。
> 
> 下面以中华人民共和国成立100周年纪念日那天（2049年10月1日）来计算是星期几，过程如下：
> 
> w=y+\[y/4\]+\[c/4\]-2c+\[26(m+1）/10\]+d-1
> 
> =49+\[49/4\]+\[20/4\]-2×20+\[26×（10+1）/10\]+1-1
> 
> =49+\[12.25\]+5-40+\[28.6\]
> 
> =49+12+5-40+28
> 
> =54 （除以7余5）
> 
> 即2049年10月1日（100周年国庆）是星期五。
> 
> 再比如计算2006年4月4日，过程如下：
> 
> w=y+\[y/4\]+\[c/4\]-2c+\[26(m+1）/10\]+d-1
> 
> =6+\[6/4\]+\[20/4\]-2\*20+\[26\*（4+1）/10\]+4-1
> 
> =-12 （除以7余5，注意对负数的取模运算！实际上应该是星期二而不是星期五)
> 
> w=（-12%7+7）%7=2；
> 
> 然后求这年这月第一天是星期几，这是为了求这年这月这日是星期几
> 
> ### （3）完整代码 ###
> 
>     import java.util.HashSet;
>     import java.util.LinkedList;
>     import java.util.List;
>     import java.util.Scanner;
>     import java.util.Set;
>     
>     /*
>      * 分解因数
>      */
>     //超时但是结果都对
>     public class DecomposingNumbers {
>         public static void main(String[] args) {
>             Scanner sc = new Scanner(System.in);
>             while (sc.hasNextInt()) {
>                 int num = sc.nextInt();
>        
>                 List <Integer>list = new LinkedList<>();
>                 for (int i = 1; i <= num; i++) { //1~num有多少个质数
>                     int temp = isFactor(i);
>                     if (temp != -1) { //是质数加入列表
>                         list.add(temp);
>                     }
>                 }
>     
>                 List<Integer>one = new LinkedList<>();
>                 List<List<Integer>>res = new LinkedList<>();
>                 DFS(0, num, 1, list, one, res);
>                 System.out.print(num + "=");
>                 for (int i = 0; i < res.size(); i++) {
>                     for (int j = 0; j < res.get(i).size(); j++) {
>                         if (j == res.get(i).size() - 1) {
>                             System.out.print(res.get(i).get(j)+" ");
>                         } else {
>                             System.out.print(res.get(i).get(j) + "*");
>                         }
>                     }
>                 }
>             }
>         }
>         public static void DFS(int index, int num, int mulRes, List<Integer>list,List<Integer> one, List<List<Integer>> res) {
>             //num目标值,list所有比num小的质数集合，one存放一种正确的组合，res结果集合;每一种正确的组合都放进结果集，mulRes当前的数，index下标位置
>             if (mulRes > num) {//当前值大于目标值
>                 return;
>             }
>             if (mulRes == num) {//当前值等于目标值，表示这个组合正确，是我们想要的
>                 List<Integer> temp = new
>                 LinkedList<>(); //临时变量，将一种组合放入结果集
>                 for (int i = 0; i < one.size(); i++) {
>                     temp.add(one.get(i));
>                 }
>                 res.add(temp);
>                 return;
>             }
>             for (int i = index; i < list.size(); i++) {
>                 if (mulRes > num) {
>                     continue;//如果当前值大于目标值就下一个，但是本题按顺序排的不会出现这种情况，可以不写
>                 }
>                 one.add(list.get(i));
>                 DFS(i, num, mulRes * list.get(i), list, one, res);
>                 one.remove(one.size() -
>                            1); //回溯，当前值如果大于等于就要回到上一步，然后不合适的质数删去走下一步
>             }
>         }
>         public static int isFactor(int num) {//判断某个数是否为质数
>             if (num == 1) {
>                 return -1;
>             }
>             if (num == 2) {
>                 return 2;
>             }
>             for (int i = 2; i < num; i++) {
>                 if (num % i == 0) {
>                     return -1;//不是返回-1
>                 }
>             }
>             return num;//是返回该值
>         }
>     }
> 
> ![61637e10d2964af7b5b3e09f199cc7a5.png][]

> ## 二、分解因数 ##
> 
> ### （1）原题再现 ###
> 
> [分解因数\_\_牛客网][Link 2]  
> 所谓因子分解，就是把给定的正整数a，分解成若干个素数的乘积，即 a = a1 × a2 × a3 × ... × an,并且 1 < a1 ≤ a2 ≤ a3 ≤ ... ≤ an。其中a1、a2、...、an均为素数。 先给出一个整数a，请输出分解后的因子。
> 
> **输入描述:**
> 
> 输入包含多组数据，每组数据包含一个正整数a（2≤a≤1000000）。
> 
> **输出描述:**
> 
> 对应每组数据，以“a = a1 \* a2 \* a3...”的形式输出因式分解后的结果。
> 
> 示例1
> 
> 输入
> 
> 10
> 
> 8
> 
> 输出
> 
> 10 = 2 \* 5
> 
> 18 = 2 \* 3 \* 3
> 
> ### （2）问题分析 ###
> 
> 我首先想到的DFS深度优先算法，把所有组合情况列举出来，但是会造成超时错误。我会把DFS的代码放到文末，有兴趣的同学可以感受一下深度优先的魅力。
> 
> 这道题和昨天的因子个数是一样，用质数去试除。例如30能被2整除，那就拿商继续除以2，除不尽就换3，一直到除到质数为止。注意输出格式。
> 
> ### （3）完整代码 ###
> 
>     import java.util.Scanner;
>     
>     /*
>      * 分解因数
>      */
>     public class Main {
>         public static void main(String[] args) {
>             Scanner sc = new Scanner(System.in);
>             while (sc.hasNextInt()) {
>                 int num = sc.nextInt();
>                 System.out.print(num + " = ");
>                 for (int i = 2; i <= num; i++) {
>                     while (num % i == 0) {
>                         if (num == i) {
>                             System.out.println(i);
>                         } else {
>                             System.out.print(i + " * ");
>                         }
>                         num /= i;
>                     }
>                 }
>             }
>         }
>     }
> 
> ![08f4b34d953b4963b87a81071a003d74.png][]

## 三、DFS深度优先列举所有可能的情况 ##

![a5ae4f880f6f4992b28c4d18eeb4d4e5.png][]

[Link 1]: https://www.nowcoder.com/questionTerminal/d95d98a2f96e49078cd7df84ba0c9d79
[f1c70800112b44f798fb1282d2f1c7d0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/606e127e83f145499bedaaa8af6075bb.png
[29ef5bc8861a4d308fe1cd35ec1632ad.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/99c50e2f3f1f471fa41ff022bb14a9a0.png
[d8d125a33dda41018444b5589d6aa367.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/94d197a2361341deb6d0feece37ddfc7.png
[61637e10d2964af7b5b3e09f199cc7a5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/4f4635ba71394d9db7e62f17d26653fb.png
[Link 2]: https://www.nowcoder.com/questionTerminal/0f6976af36324f8bab1ea61e9e826ef5
[08f4b34d953b4963b87a81071a003d74.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/66fd6defd03e4071b59382781ef045fb.png
[a5ae4f880f6f4992b28c4d18eeb4d4e5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/d663ffd14165432c8d25dc183b967949.png