2017b

Материал из PTHSWiki
Перейти к: навигация, поиск

Содержание

Рекурентные соотношения

import java.util.Scanner;

public class Main {
        public static int f (int n) {
                if (n == 0) {
                        return 1;
                }
                if (n == 1) {
                        return 1;
                }
               
                return f(n-1) + f(n-2);
        }
       
        public static int A (int n, int m) {
                if (n == 0) {
                        return 1;
                }
                if (m == 0) {
                        return 1;
                }
               
                return A(n-1, m) + A(n, m-1);
        }
       
        public static void main(String[] args) {
                Scanner sc = new Scanner(System.in);
                int a = sc.nextInt();
                int b = sc.nextInt();
                System.out.println(A(a, b));
        }
}

Сортировка массива по своему правилу

import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;
import java.util.Scanner;

class Point {
        int x, y;
        String name;
}

public class Main {
        public static void main(String[] args) {
                Point[] arr = new Point[10];
               
                Random r = new Random();
                for (int i = 0; i < arr.length; i++) {
                        arr[i] = new Point();
                        arr[i].x = r.nextInt(100);
                        arr[i].y = r.nextInt(100);
                        arr[i].name = "Point" + i;
                }
               
                Arrays.sort(arr, new Comparator<Point>() {

                        @Override
                        // надо вернуть 1, если первая точка больше
                        // надо вернуть -1, если первая точка меньше
                        // надо вернуть 0, если они равны
                        public int compare(Point o1, Point o2) {
                                if (o1.x > o2.x) {
                                        return 1;
                                }
                                if (o1.x < o2.x) {
                                        return -1;
                                }
                                return 0;
                        }
                });
               
                for (int i = 0; i < arr.length; i++) {
                        System.out.println(arr[i].x + " " + arr[i].y + " " + arr[i].name);
                }
        }
}

Создание своего класса, являющегося «Сравниваемым» (Comparable)

        class Student implements Comparable<Student> {
                String lastName, firstName;

                @Override
                public int compareTo(Student that) {
                        int lastNameComparison = this.lastName.compareTo(that.lastName);
                        if (lastNameComparison != 0) {
                                return lastNameComparison;
                        }
                        return this.firstName.compareTo(that.firstName);
                }
               
                @Override
                public String toString() {
                        return this.firstName + " " + this.lastName;
                }
        }


Сортировка двумерного массива

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;


public class Main3 {
        public static void main(String[] args) {
                int N;
                Scanner sc = new Scanner(System.in);
               
                N = sc.nextInt();
               
                int[][] a = new int[N][2];
                for (int i = 0; i < N; i++) {
                        a[i][0] = sc.nextInt();
                        a[i][1] = sc.nextInt();                
                }
       
                Arrays.sort(a, new Comparator<int[]>() {
                        @Override
                        public int compare(int[] o1, int[] o2) {
                                int p = o1[0]*o1[0]+o1[1]*o1[1];
                                int q = o2[0]*o2[0]+o2[1]*o2[1];
                               
                                if (p > q) {
                                        return 1;
                                }

                                if (p < q) {
                                        return -1;
                                }
                               
                                return 0;
                        }
                });
               
                for (int i = 0; i < N; i++) {
                        System.out.println(a[i][0] + " " + a[i][1]);
                }
        }
}

Создание классов

import java.util.Random;
import java.util.Scanner;

class Pupil {
        int weight;
        int height;
        boolean sex;
        String name;
}

public class Main4 {

        public static void main(String[] args) {
                Pupil[] cl = new Pupil[11];
               
                Scanner sc = new Scanner(System.in);
                Random r = new Random();
               
                for (int i = 0; i < 11; i++) {
                        cl[i] = new Pupil();
                        cl[i].name = sc.nextLine();
                        cl[i].weight = 40+r.nextInt(50);
                        cl[i].height = 150+r.nextInt(50);
                        cl[i].sex = r.nextBoolean();
                }
               
                for (int i = 0; i < 11; i++) {
                        System.out.print(cl[i].name + " " + cl[i].height + " " + cl[i].weight + " ");
                        if (cl[i].sex == true) {
                                System.out.println("Male");
                        } else {
                                System.out.println("Female");
                        }
                }
        }

}

Сортировка массивов по своему правилу

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


public class Main3 {

        public static void main(String[] args) {
                Integer[] arr = new Integer[100];
               
                Random r = new Random();
                for (int i = 0; i < arr.length; i++) {
                        arr[i] = r.nextInt(100);
                }
       
                Arrays.sort(arr, new Comparator<Integer>() {

                        @Override
                        public int compare(Integer o1, Integer o2) {
                                if (o1%5 > o2%5) {
                                        return 1;
                                }
                                if (o2%5 > o1%5) {
                                        return -1;
                                }
                               
                                if (o1 > o2) {
                                        return 1;
                                }
                                if (o2 > o1) {
                                        return -1;
                                }
                                return 0;
                        }
                });
       
                System.out.println(Arrays.toString(arr));
        }

}

Бинарный поиск (в массиве)

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


public class Main {

        public static void main(String[] args) {
                int[] arr = new int[100];
               
                Random r = new Random();
                for (int i = 0; i < arr.length; i++) {
                        arr[i] = r.nextInt(20);
                }
                Arrays.sort(arr);
               
                int x = 12;
               
                int beg = 0;
                int end = arr.length;
                int flag = -1;
               
                while (beg != end) {
                        int m = (beg+end)/2;
                        if (arr[m] == x) {
                                flag = m;
                                break;
                        }
                        if (arr[m] > x) {
                                end = m;
                        } else {
                                beg = m + 1;
                        }
                }
               
                System.out.println(flag);
        }

}

Бинарный поиск (корень энной степени)

public class Main2 {

        public static void main(String[] args) {
                int n = 2;
                int a = 9;
               
                double beg = 0;
                double end = a+1;
                double flag = -1;
                double m = 0;
               
                while (end-beg >= 1e-15) {
                        m = (beg+end)/2;
                        double t = Math.pow(m, n);
                        if (t == a) {
                                flag = m;
                                break;
                        }
                        if (t > a) {
                                end = m;
                        } else {
                                beg = m;
                        }
                }
               
                System.out.println(m);
        }

}

НОД и время работы

import java.util.Random;

public class Main {
        public static int gcd1(int a, int b) {
                if (a * b == 0) {
                        return a + b;
                }
                if (a > b) {
                        return gcd1(a % b, b);
                }
                return gcd1(a, b % a);
        }

        public static int gcd2(int a, int b) {
                while (a * b != 0) {
                        if (a > b) {
                                a = a % b;
                        } else {
                                b = b % a;
                        }
                }
                return a + b;
        }

        public static int gcd3(int a, int b) {
                while (a * b != 0) {
                        if (a > b) {
                                a = a - b;
                        } else {
                                b = b - a;
                        }
                }
                return a + b;
        }

        public static void main(String[] args) {
                Random r = new Random();

                long t = System.currentTimeMillis();

                for (int i = 0; i < 10000000; i++) {
                        int a = r.nextInt(2000000000);
                        int b = r.nextInt(2000000000);
                        int c = gcd1(a, b);
                }

                System.out.println(System.currentTimeMillis() - t);
               
        }
}
Личные инструменты
Пространства имён
Варианты
Действия
Навигация
Инструменты