第一次回复发表于31# 昨天 21:49~
该中饭了,先发前两道~
第一题:- import java.util.Scanner;
- /*
- * 题目1:键盘录入一个正整数,将其分解质因数。如:输入30,打印出30=2*3*5。
- *
- * 分析: 应用递归的方法求解。
- * 从2开始取模数对录入的正整数进行取模,如果模为零,则二者相除的结果作为被模数继续递归取模,
- * 如果模不为0,则被模数不变,模数加1,继续递归,直到模数增加到被模数的1/2以上。
- *
- */
- public class Test1 {
- public static void main(String[] args) {
- //从控制台获取一个整数
- Scanner in = new Scanner(System.in);
- System.out.print("请输入一个正整数:");
- int i = in.nextInt();
- //调用递归方法获取结果
- diGui(i,2,i);
- }
- /**
- * 递归方法,将输入的正整数进行分解为质因数并输出
- * @param a 被模数
- * @param b 模数
- * @param x 控制台输入的原值
- */
-
- //只为完成题目要求,就private好了。
- private static void diGui(int a, int b, final int x){
- //结束条件:当b大于a的一半时输出最后一个被模数,如果被模数一直无变化,说明是质数。
- if(a < b * 2){
- if(a != x)
- System.out.println(a);
- else
- System.out.println("您输入的是一个质数,无法分解");
- return;
- }
- //如果可整除,则继续用此数进行递归,否则将被模数+1。
- else if(a % b == 0){
- if(a == x)
- System.out.print(x + "= ");
- System.out.print(b + "* ");
- diGui(a / b, b, x);
- }else
- diGui(a, b + 1, x);
- }
- }/* Output:
- 请输入一个正整数:90
- 90= 2* 3* 3* 5
- *///:~
复制代码 第二题:- import java.util.ArrayList;
- import java.util.Arrays;
- import java.util.Random;
- /*
- * 题目2:求出1-100之间的素数,假设有n个,将这些素数存入a[n+1]的数组中。
- * (其中n个是求出的各个素数,还有一个是随机添加其中的一个素数)
- * 这样数组中就有相同的两个素数,写一个搜索算法,找出数组中相同的那个素数。
- * (随机添加的素数,可手动指定,也可利用随机方法产生)
- * (注:存入数组后,数组中的所有元素理论上是无序的,相同的那个素数不一定就等于a[n],
- * 而是被存入了数组中的某个角标上)
- *
- * 分析: 首先要找出1-100之间的素数。素数的判断可以用二重循环嵌套,也可以用递归,这里用
- * for循环嵌套,外层枚举数,内层枚举2~sqrt(外层数字)之间的数对外层数取模。内层枚举结束
- * 依然没找到模0的数则外层为素数。
- *
- * 因为找到的素数不是直接打印而是放在数组中,而查找过程结束前找到的素数个数未知,
- * 因此使用ArrayList临时存放找到的素数,之后根据ArrayList中元素的个数确定数组大小,再
- * 将其移动到数组内。
- *
- * 因为要在数组中添加一个重复的素数,所以数组大小可以定义为实际素数大小加1。再移入数组时,先
- * 随机产生一个角标,移入时跳过此位置,之后再在素数中随机找一个放入此位,至此a[n+1]数组就搞定了。
- *
- * 之后要解决的就是如何在一个无序数组中找到重复元素,可以使用排序后临位比较的方法,但效率较低,
- * 因此可以使用类似选择排序的方式查找重复,但不进行换位操作,这样效率较高。
- *
- */
- public class Test2 {
- public static void main(String[] args) {
- //定义一个ArrayList用于临时存储找到的素数
- ArrayList<Integer> list = new ArrayList<Integer>();
-
- //嵌套循环寻找素数,找到后插入到list中,模数限定不大于被模数的平方根,以提高效率
- for(int i = 2; i <= 100; i++){
- for(int j = 2;; j++){
- if(j > (int)Math.sqrt(i)){
- list.add(i);
- break;
- }
- if(i % j == 0)
- break;
- }
- }
-
- //输出找到的list,这里直接调用了list的toString方法。
- System.out.println("1-100之间的素数有:\n" + list);
-
- //创建了一个int数组,大小为素数个数+1
- int size = list.size();
- int[] arr = new int[size + 1];
-
- //生成随机数,randomNum为随机生成的1-100中的某素数,randomPos是插入数组中的位置
- //这样可以让每次运行时插入的数和插入的位置都不同
- Random rand = new Random();
- int randomNum = list.get(rand.nextInt(size));
- int randomPos = rand.nextInt(size);
-
- //下面将ArrayList中的元素移动到数组中,在随机位插入随机素数,在尾位插入跳过的素数
- for(int i = 0; i < arr.length - 1; i++){
- if(i == randomPos){
- arr[i] = randomNum;
- continue;
- }
- arr[i] = list.get(i);
- }
- arr[arr.length - 1] = list.get(randomPos);
-
- //输出完成插入后的数组
- System.out.println("插入随机素数之后的数组为:\n" + Arrays.toString(arr));
-
- //使用类似选择排序的方式进行多次比较,但不交换元素的位置,即实际不排序
- for(int i = 0; i < arr.length -1; i++){
- for(int j = i + 1; j < arr.length; j++){
- if(arr[i] == arr[j])
- System.out.println("重复元素为" + arr[i] + " ,出现位置为角标" + i + "和角标" + j);
- }
- }
- }
- }/* Output:
- 1-100之间的素数有:
- [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
- 插入随机素数之后的数组为:
- [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 11, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 47]
- 重复元素为11 ,出现位置为角标4和角标14
- *///:~
复制代码 |