【c++笔试强训】（第十一篇）
目录
拼三⻆（枚举/dfs）
题目解析
讲解算法原理
编写代码
求最⼩公倍数（数学）
题目解析
讲解算法原理
编写代码
拼三⻆（枚举/dfs）
题目解析
1.题目链接：登录—专业IT笔试面试备考平台_牛客网
2.题目描述
给出6根棍子，能否在选出3根拼成一个三角形的同时剩下的3根也能组成一个三角形？
输入描述:
首先在一行中给出一个 t,1≤t≤103t,1 \le t \le 10^3t,1≤t≤103，代表测试数据的组数
接下来t行，每行给出6个数字代表棍子长度，棍子长度为正且小于10910^9109
输出描述:
在一行中输出 “Yes” or “No”
示例1
输入
2 1 1 1 1 1 1 1 2 3 4 5 6
2
1 1 1 1 1 1
1 2 3 4 5 6输出
Yes No
Yes
No
讲解算法原理
解法：
算法思路：
简单枚举，不过有很多种枚举⽅法，我们这⾥之间⽤简单粗暴的枚举⽅式。
编写代码
c++算法代码：
#include <iostream>
#include <algorithm>
using namespace std;
int t;
int arr[6];
int main()
{
cin >> t;
while(t--)
{
for(int i = 0; i < 6; i++) cin >> arr[i];
sort(arr, arr + 6);
if(arr[0] + arr[1] > arr[2] && arr[3] + arr[4] > arr[5] ||
arr[0] + arr[2] > arr[3] && arr[1] + arr[4] > arr[5] ||
arr[0] + arr[3] > arr[4] && arr[1] + arr[2] > arr[5] ||
arr[0] + arr[4] > arr[5] && arr[1] + arr[2] > arr[3])
{
cout << "Yes" << endl;
}
else cout << "No" << endl;
}
return 0;
}java算法代码：
import java.util.*;
public class Main
{
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
int t = in.nextInt();
int[] arr = new int[6];
while(t-- != 0)
{
for(int i = 0; i < 6; i++) arr[i] = in.nextInt();
Arrays.sort(arr);
if(arr[0] + arr[1] > arr[2] && arr[3] + arr[4] > arr[5] ||
arr[0] + arr[2] > arr[3] && arr[1] + arr[4] > arr[5] ||
arr[0] + arr[3] > arr[4] && arr[1] + arr[2] > arr[5] ||
arr[0] + arr[4] > arr[5] && arr[1] + arr[2] > arr[3])
{
System.out.println("Yes");
}
else
{
System.out.println("No");
}
}
}
}
求最⼩公倍数（数学）
题目解析
1.题目链接：求最小公倍数_牛客题霸_牛客网
2.题目描述
描述
正整数A和正整数B 的最小公倍数是指 能被A和B整除的最小的正整数值，设计一个算法，求输入A和B的最小公倍数。
数据范围：1 \le a,b \le 100000 \1≤a,b≤100000
输入描述：
输入两个正整数A和B。
输出描述：
输出A和B的最小公倍数。
示例1
输入：
5 7
输出：
35
示例2
输入：
2 4
输出：
4
讲解算法原理
解法：
算法思路：
A和B的最⼩公倍数=A*B/两者的最⼤公约数。最⼤公约数：辗转相除法。
编写代码
c++算法代码：
#include <iostream>
using namespace std;
int gcd(int a, int b)
{
if(b == 0) return a;
return gcd(b, a % b);
}
int main()
{
int a, b;
cin >> a >> b;
cout << (a * b / gcd(a, b)) << endl;
return 0;
}java算法代码：
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息public class Main
{
public static int gcd(int a, int b)
{
if(b == 0) return a;
return gcd(b, a % b);
}
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
int a = in.nextInt(), b = in.nextInt();
System.out.println(a * b / gcd(a, b));
}
}