java--《算法设计与分析》算法实验一

实验内容

编写一个程序，随机产生10个1-20的整数，设计一个高效算法，找其中的最大元素和最小元素，并统计元素之间的比较次数。调用该算法执行10次并求元素的平均比较次数。

import java.util.Random;

public class Test {
    public final static int MAXN = 100;
    public static void main(String[] args){
        int a[] = new int[MAXN];
        int m,sumcomp = 0,count = 0;
        Integer comp = 0;


        for(m=1;m<=10;m++)
        {
            System.out.printf("第%d组",++count);
            randa(a,10);
            comp = MaxMin(a,10);
            sumcomp+=comp;
        }
        System.out.printf("平均比较次数=%g\n",1.0*sumcomp/10);
    }


    private static void randa(int[] a, int i) {
        for(i=0;i<a.length;i++)
            a[i] = new Random().nextInt(20);
    }


    private static Integer MaxMin(int[] a, int n) {
        int i,max,min;
        int comp = 0;
        max = min = a[0];
        for(i=0;i<n;i++){
            comp++;
            if(a[i]>max)
                max = a[i];
            else
            {
                comp++;
                if (a[i]<min)
                    min = a[i];
            }
        }
        for(i=0;i<n;i++)
            System.out.printf("%3d",a[i]);
        System.out.printf(":最大值%d,最小值%d,比较次数=%d\n",max,min,comp);
        return comp;
    }
}

输出结果：

一个平方和三元组 (a,b,c) 指的是满足 a2+ b2 = c2 的整数三元组 a，b 和 c 。

给你一个整数 n ，请你返回满足 1<= a, b, c <= n 的平方和三元组的数目。

示例 1：

输入：n = 5

输出：2

解释：平方和三元组为(3,4,5) 和 (4,3,5) 。

示例 2：

输入：n =10

输出：4

解释：平方和三元组为(3,4,5)，(4,3,5)，(6,8,10) 和(8,6,10) 。

提示：1<= n <= 250

public class Test1 {
    public static int countTriples(int n){
        int res = 0;//定义计算满足平方和三元数组的数目
        for(int a = 1;a<=n;a++){
            for(int b=1;b<=n;b++){
                int cs = a*a +b*b;
                int c = (int)Math.sqrt(cs);
                if(c<=n && c*c ==cs){
                    res++;
                    System.out.println("三个数为"+a+","+b+","+c+",和为"+cs);
                }
            }
        }
     return res;
    }
    public static void main(String[] args){
        System.out.println(countTriples(25));
    }
}

输出结果：

1. 设计方法，判断数组是有序的

import java.util.Arrays;
import java.util.Random;

public class Test2 {
    public static void main(String[] args) {
        int[] array = new int[]{1, 2, 4, 3};
        System.out.printf(Arrays.toString(array));

        judgeArr(array);
    }

    private static void judgeArr(int[] arr) {
        int flag = 0;//0:相等; 1:递增; -1:递减;
        int i = 0;
        for (i = 0; i < arr.length - 1; i++) {
            if (arr[i] == arr[i + 1]) {
                flag = 0;
            } else {
                if (arr[i] > arr[i + 1]) {
                    flag = -1;
                }
                else{
                    if (arr[i] < arr[i+1]){
                        flag = 1;
                    }
                }
                break;
            }
        }
        System.out.printf("数组前几位是有序的," + (flag > 0 ? "递增的" : (flag < 0 ? "递减的" :(flag > 0? "相等的" :0))));

        if (flag == 0) {//相等序列
            System.out.printf("数组是有序的，由相等的数字组成的");
        } else {
            int j = i;
            if (flag > 0) {//初步判断是递增序列
                for (; j < arr.length - 1; j++) {
                    if (arr[j] > arr[j + 1]) {//出现了递减情况，说明是乱序
                        break;
                    }
                }
            } else {//初步判断是递减序列
                for (; j < arr.length - 1; j++) {
                    if (arr[j] < arr[j + 1]) {//出现了递增情况，说明是乱序
                        break;
                    }
                }
            }
            if (j == arr.length - 1) {//和之前初步判断的结果是一样
                System.out.printf("数组是有序的，" + (flag > 0 ? "递增的" : (flag < 0) ? "递减的" : "相等的"));
            } else {
                System.out.printf("数组是无须的");
            }
        }
    }
}

输出结果：

1. 设计和实现二维矩阵的输入和转置

public class Test3 {
    public static void main(String[] args) {
        int[][] a = new int[][]{{1,2,3},{4,5,6},{7,8,9}};
        int n = a.length;//行数
        int m = a[0].length;//列数
        int[][] arr = new int[n][m];

        for(int i = 0; i<n;i++){
            for(int j = 0;j<m;j++) {
                arr[i][j] = a[j][i];//转置
            }
        }
       //输出
        for(int i = 0;i<n;i++){
            for(int j = 0;j<m;j++){
                System.out.printf(arr[i][j]+" ");
            }
            System.out.println(" ");
        }
    }
}

输出结果：