Skip to content
BranchesTags

Latest commit

 

History

23 Commits

Folders and files

NameName
Last commit message
Last commit date
README.md
README.md
 
 
T1.java
T1.java
 
 
T2.java
T2.java
 
 
T3.java
T3.java
 
 
T4.java
T4.java
 
 

Repository files navigation

Отчет по лабораторной работе № 2

№ группы: ПМ-2501

Выполнил: Попов Роман Алексеевич

Вариант: 13

Cодержание:

1. Постановка задачи

Ваша задача – посмотреть, какие значения принимает последовательность при разных a0 и n, вывести закономерность, по которой строится последовательность и запрограммировать ее самостоятельно.

1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4 - первые 30 элементов последовательности. Можно заметить, что каждая цифра последовательности соответствует количеству единиц в двоичной форме записи числа, то есть числу один соответствует 1, двойке - 1 (10 в 2сс), тройке - 2 (11 в 2 сс), и тд. Соответсвенно необходимо написать программу, которая выводит на экран количество единиц в двоичной записи натурального числа.

2. Входные и выходные данные

Данные на вход

На вход программа получает только 1 число, которое также является длиной последовательности, так как искомый ряд не зависит от первого элемента. Так как количество элементов - это натуральное число, воспользуемся типом данных int.

Тип min значение max значение
n (Число 1) Натуральное число 1 231-1

Данные на выход

В программе данные не хранятся, а сразу выводится результат, который является натуральным числом.

3. Выбор структуры данных

Программа получает натуральное число, не превышающее 231-1. Для его хранения потребуется 1 переменная n типа int.

4. Алгоритм

  1. Ввод данных:
    Программа считывает натуральное числ n.

  2. Перевод в двоичную систему:
    Программа переводит числа от 1 до n в двоичную систему счисления.

  3. Вывод результата:
    На экран выводится поочередно количество единиц в двоичной форме записи числа, принадлежащему промежутку от 1 до n.

5. Программа

import java.io.PrintStream;
import java.util.Scanner;

public class T1 {
    public static Scanner in = new Scanner(System.in);
    public static PrintStream out = System.out;
    static String dv(int a){
        if (a == 0)
            return " ";
        return dv(a/2) + " "  + a % 2;
    }

    public static void main(String[] args) {
        int n = in.nextInt();
        for (int i = 1; i <= n; i++){
            String w = dv(i);
            int q = 0;
            for (int j = 0; j < w.length(); j++){
                if (w.charAt(j) == '1')
                    q++;
            }
            out.print(q + " ");
        }
    }
}

6. Анализ правильности решения

Программа выводит последовательность, совпадающую с последовательностью из условия.

  • Input:

    30

  • Output:

    1 1 2 1 2 2 3 1 2 2 3 2 3 3 4 1 2 2 3 2 3 3 4 2 3 3 4 3 4 4

Cодержание:

7. Постановка задачи

Дана последовательность из n чисел. Найти самую длинную подпоследовательность идущих подряд элементов, которую можно сделать возрастающей, удалив из нее 1 элемент. Вывести ее длину и индексы первого элемента и элемента, который необходимо убрать. Если таких подпоследовательностей несколько, вывести результат для той, что встречается раньше остальных.

В данной задачи нам необходимо сравнивать соседние числа, пока мы не наткнемся на ситуацию: правое число больше левого. В таком случае мы удаляем этот элемент, пропуская его. Если эта ситуация повторяется, то мы проверяем, получили ли мы максимальную подпоследовательность: Если да, то запоминаем длину и искомые индексы и начинаем проверку, начиная с удаленного элемента. Иначе просто начинаем проверку с удаленного элемента. После прохождения цикла выводим найденные значени (индексы в последовательности нумеруются с 1).

8. Входные и выходные данные

Данные на вход

На вход программа получает число n - количество элементов последовательности - и сам ряд элементов. Элементы последовательности будет необходимо хранить в списке. Для всех переменных воспользуемся типом данных int.

Тип min значение max значение
n (Число 1) Натуральное число 1 231-1
Ряд из n чисел Целые числа -231 231-1

Данные на выход

Для вывода нам потребуется 3 целочисленных переменных. m - максимальная длина подпоследовательности, это натуральная величина. ind0 - индекс элемента, с которого мы начинаем последовательность. indD0 - индекс элемента, который мы удаляем (он может быть равен 0, что означает, что никакой элемент удалять не нужно).

Тип min значение max значение
m (Число 1) Натуральное число 1 231-1
ind0 (Число 2) Натуральное число 1 231-1
indD0 (Число 3) Целое число 0 231-1

9. Выбор структуры данных

Программа получает натуральное число, не превышающее 231-1. Затем еще ряд целых чисел принадлежащих промежутку от -231 до 231-1. Для хранения первого числа воспользуемся переменной типа int, а для последовательности потребуется массив длинны n, хранящий значения типа int.

10. Алгоритм

  1. Ввод данных:
    Программа считывает натуральное число, обозначенное как n. Затем заполняет массив a из введенных элементов.

  2. Начальный индекс: Программа выбирает индекс, с которого начинает исследовать введенную последовательность и переменный индекс (индекс левого элемента).

  3. Сравнение чисел, если правое больше: Программа сравнивает два рядом стоящих числа

    Если правое больше:

    a) Если еще никакой элемент не был удален из последовательности, то увеличиваем на 1 счетчик длины последовательности и индекс левого числа в сравнении.

    b) Иначе индекс левого числа в сравнении становится равным индексу правого числа и увеличиваем счетчик длины последовательности на 1.

  4. Сравнение чисел, если правое меньше:

  5. Иначе, если левое больше: a) Если еще никакой элемент не был удален из последовательности, то меняем флаг отвечающий за удаленные элементы, запоминаем индекс удаленного (пропущенного) элемента и увеличиваем на 1 счетчик длины последовательности.

    b) Иначе сравниваем значение получившийся длины со значением максимальной длины. Если получившееся значения больше, то запоминаем его как максимальное значение, запоминаем индекс первого элемента подпоследовательности и индекс удаленного элемента из подпоследовательности. Возвращаем в начальное значение флаг, индекс начального элемента, индекс удаленного элемента и счетчик длины, а переменный индекс становится индексом удаленного элемента (до возвращения в начальное значение).

  6. Вывод результата:
    На экран выводятся: максимальная длинна подпоследовательности, индекс первого элемента подпоследовательности, индекс удаленного элемента из подпоследовательности.

11. Программа

Полный текст программы с комментариями на русском языке

import java.io.PrintStream;
import java.util.Scanner;

public class T1 {
    public static Scanner in = new Scanner(System.in);
    public static PrintStream out = System.out;
    public static void main(String[] args) {
        int n = in.nextInt(); // Ввод длины последовательности
        int c = 0; // Переменный счетчик длины
        int k = 1; // Флаг удаленного элемента
        int ind1 = -1; // Индекс начального элемента исследуемой последовательности
        int ind0 = 0; // Индекс начального элемента максимальной подпоследовательности
        int indD = -1; // Индекс "удаленного" элемента исследуемой последовательности
        int indD0 = 0; // Индекс "удаленного" элемента максимальной подпоследовательности
        int indz = 0; // Переменный индекс
        int m = 0; //Длина максимальной последовательности
        int[]a = new int[n]; // Задаем массив, где будем хранить последовательность
        for (int i = 0; i<n; i++){
            a[i] = in.nextInt(); // Ввод последовательности
        }
        for (int i = 1; i<n; i++){
            if (ind1 == -1) { // Если индекс начального элемента имеет начальное значение, то задаем его и переменный индекс
                ind1 = i - 1;
                indz = i - 1;
            }
            if (a[indz] < a[i]){ // Сравниваем соседние числа
                if (k == 1) { // Если элемент не удален и числа подходят, то увеличиваем левый индекс и длину на 1
                    c++;
                    indz++;
                }
                else{ // Иначе (числа все еще подходят) увеличиваем длину, а левый индекс становится правым, чтобы проскочить удаленный элемент
                    c++;
                    indz = i;
                }
            }
            else // Если не подходят (левое больше или равно правому)
                if (k == 1){ // Если еще не удаляли элемент, то меняем флаг, запоминаем индекс удаленного и увеличиваем длину
                    k = 0;
                    indD = i;
                    c++;
                }
                else{
                    if (m < c) { //Иначе сравниваем максимальную длину с переменной. Если максимальная меньше, то она становится переменной. Также запоминаем индексы начального и удаленных элементов
                        m = c;
                        indD0 = indD;
                        ind0 = ind1;
                    }
                    k = 1; // Возвращаем в начальное значения все элементы кроме счетчика цикла
                    ind1 = -1;
                    i = indD; // Его мы делаем равным индексу удаленного элемента, чтобы новая последовательность, которую мы исследуем, содержала все значимые числа
                    indD = -1;
                    c = 0;
                }
        }
        if (m < c && m == 0) { // Эта проверка нужна, потому что если исходная последовательность была подходящий по условию (то есть изначально возрастающая или нужно было удалить только один элемент и она сразу становилась максимальной возрастающий, то есть не нужно было проверять остальные подпоследовательности
            m = c;
            indD0 = indD;
            ind0 = ind1;
        }
        out.println("Макс. длина подпоследовательности:" + " " + (m + 1));
        out.println("Индекс первого элемента подпоследовательности:" + " " + (ind0 + 1));
        out.println("Индекс удаленного элемента:" + " " + (indD0 + 1));
    }
}

12. Анализ правильности решения

Нам необходимо удалить 4 элемент, тогда будем иметь возрастающую подпоследовательность из всех оставшихся чисел.

  • Input:

    7
1 2 4 3 5 6 7

  • Output:

    7 1 4

Удалять элементы не нужно, так как исходная последовательность сразу является подходящей под условие.

  • Input:

    5
1 2 3 4 5

  • Output:

    5 1 0

Первая подпоследовательность максимальной длины - 1 3 2 4 6 (необходимо удалить третий элемент, то есть двойку)

  • Input:

    6
1 3 2 4 6 5

  • Output:

    5 1 3

Cодержание:

13. Постановка задачи

Дано целое положительное число n. Найти длину периодической части в десятичной записи дроби 1/n. Если дробь конечная (например, 1/2 = 0.5), вывести 0. Для решения этой задачи есть несколько способов. Оптимальный способ который я знаю реализуется с помощью свойства: длина периода является наименьшим положительным числом e, для которого выполняется условие 10e % n == 1. Для реализации этого метода будет необходимо убрать из n все простые множители 2 и 5, так как при делении на произведение этих чисел в любой степени мы не получаем период. Затем будем увеличивать значение e, чтобы выполнилось условие. Также, чтобы не хранить в памяти слишком большие числа, так как длина периода может быть, например, 366(для числа 1101), то число 10366 выходит за известные мне типы данных. Значит целесообразней не сравнивать 10e по модулю n с 1, а сначала сравнить остаток 10 % n с 1. Если этот остаток не равен одному, но мы находим новый остаток 10 % n * 10 % n и так далее, пока не получим равенство с 1.

14. Входные и выходные данные

Данные на вход

На вход программа получает натуральное число n - знаменатель дроби 1/n. Для переменной воспользуемся типом данных int.

Тип min значение max значение
n (Число 1) Натуральное число 1 231-1

Данные на выход

Для вывода нам потребуется хранить лишь одну переменную e, которая является целым натуральным числом. Для переменной воспользуемся типом данных int.

Тип min значение max значение
e (Число 1) Натуральное число 1 231-1

15. Выбор структуры данных

Программа получает натуральное число n, не превышающее 231-1. Нам необходимо хранить и его, и еще две переменные: первую, отвечающую за степени десятки, вторую, хранящую остатки. Все три числа натуральные, значит воспользуемся типом данных int.

16. Алгоритм

  1. Ввод данных:
    Программа считывает натуральное число n.

  2. "Отчистка n": Программа делит n на 5 и 2, пока n имеет в своем разложении на простые множители эти числа. Если после этого n == 1, то мы выводим 0 (так как имеем конечную дробь).

  3. Проверка 10e % n == 1: Если n не равна 1, то задаем переменную хранящую остатки и изначально равную 10 % n. Пока она не равна 1, мы меняем ее так: Старое значение * 10 % n. Также увеличиваем е на 1.

  4. Вывод результата:
    На экран выводится e, если до этого не было вывода 0.

17. Программа

Полный текст программы с комментариями на русском языке

import java.io.PrintStream;
import java.util.Scanner;
public class T3 {
    public static Scanner in = new Scanner(System.in);
    public static PrintStream out = System.out;
    public static void main(String[] args) {
        out.println("Введите n - знаменатель дроби 1/n");
        int n = in.nextInt(); // Вводим знаменатель дроби
        int e = 1;
        while (n % 2 == 0 || n % 5 == 0) { // Избавляем знаменатель от множителей 2 и 5
            if (n % 2 == 0)
                n = n / 2;
            else
                n = n / 5;
        }
        if (n == 1) // Если знаменатель состоял только из чисел 2 и 5, то выводим 0, так как такой знаменатель не давал периодичности дроби
            out.print(0);
        else {
            int w = 10 % n; // Задаем первый остаток
            while (w != 1) {
                w = w * 10 % n; // Запоминаем следующий остаток, параллельно увеличивая степень 10
                e++;
            }
            out.print(e);
        }
    }
}

18. Анализ правильности решения

Для числа 3 длина периода известна всем.

  • Input:

    3

  • Output:

    1

Для числа состоящего из 2 и 5 (например 10).

  • Input:

    10

  • Output:

    0

Для числа, дающего большую периодичность.

  • Input:

    1101

  • Output:

    366

Cодержание:

19. Постановка задачи

Дан массив из n чисел. Проверить, есть ли три элемента, расстояние между любыми двумя из которых не превышает k, и при этом их значения образуют арифметическую прогрессию. Если такие элементы существуют – выведите их в порядке появления в массиве. Если таких элементов нет – выведите "NO". Мы должны проверять элементы массива и сравнивать их друг с другом, причем последний индекс элемента, который мы можем взять за первый элемент из тройки равняется n-3, так как следующий индекс не будет иметь двух соседов справа.

20. Входные и выходные данные

Данные на вход

На вход программа получает натуральное число n - длина последовательности, натурльное число k - расстояние между элементами. Для этих данных воспользуемся типом данных int. Также программа получает на вход массив - данную последовательность, элементы которой имееют тип данных int.

Тип min значение max значение
n (Число 1) Натуральное число 1 231-1
Ряд из n чисел Целые числа -231 231-1
k (Число 2) Натуральное число 1 231-1

Данные на выход

Для вывода не придется дополнительно хранить значения элементов. Если они задают арифметическую прогрессию, то они сразу выводятся.

21. Выбор структуры данных

Программа получает натуральные числа n и k, не превышающие 231-1. Нам необходимо хранить их и ряд чисел, для которых будет использоваться целочисленный массив. Также будет необходимо хранить "флаг", который будет указывать, если ли подходящая тройка. Значит воспользуемся типом данных int.

22. Алгоритм

  1. Ввод данных:
    Программа считывает натуральные числа, обозначенные как n и k, а также ряд целых чисел, записывающихся в массив.

  2. Сравнение чисел в тройке: Мы начинаем анализировать массив, начиная с первого элемента. Сначала мы закрепляем первый элемент. После этого поочередно закрепляем элементы от элемента с индексом "первого элемента плюс один", до элемента с индексом "первого элемента плюс k минус 1". Третий элемент будет изменяться от элемента с индексом "второго закрепленного элемента плюс один", до элемента с индексом "первого элемента плюс k".

  3. Вывод результата:
    Если разность между первым закрепленным и вторым закрепленным равняется разности между вторым закрепленным и третьим закрепленным, то мы выводим эти три элемента и меняем значения флага. Если значение флага не изменено, то нужные числа не найдены, значит выводим "NO".

23. Программа

Полный текст программы с комментариями на русском языке

import java.io.PrintStream;
import java.util.Scanner;
public class T4 {
    public static Scanner in = new Scanner(System.in);
    public static PrintStream out = System.out;
    public static void main(String[] args) {
        int n = in.nextInt(); // Ввод длины последовательности
        int[]a = new int[n];
        int f = 0;
        for (int i = 0; i < n; i++)
            a[i] = in.nextInt(); // Вносим последовательность в массив
        int k = in.nextInt(); // Вводим максимальное расстояние между двумя элементами тройки
        for (int i = 0; i <= n - 3; i++){ // Перебираем первые элементы
            for (int j = i + 1; j <= k + i - 1; j++){ // Перебираем вторые элементы
                for (int z = j+1; z <= k + i && z < n; z++){ // Перебираем третьи элементы
                    if (a[i] - a[j] == a[j] - a[z]) { // Проверяем на арифметическую прогрессию
                        out.println(a[i] + " " + a[j] + " " + a[z]); // Выводим значения тройки и меняем флаг
                        f = 1;
                    }
                }
            }
        }
        if (f == 0)
            out.print("NO"); // Если условие не выполнилось, выводим "NO"
    }
}

24. Анализ правильности решения

Для данного ввода ответ будет 5 4 3, так как расстояние между любыми из этих двух элементов не превышает 3.

  • Input:

    5
1 5 2 4 3
3

  • Output:

    5 4 3

Для данного ввода все три рядом стоящих элемента создают нужные тройки, также создают тройку числа 1 3 5, потому что расстояние между каждым из них не больше 4.

  • Input:

    5
1 2 3 4 5
4

  • Output:

    1 2 3
1 3 5
2 3 4
3 4 5

Если вводить абсолютно случайные числа, то очень часто вывод будет "NO", так как для данного условия нужно подбирать специальные массивы.

  • Input:

    5
134 1523 1324 4513 51
4

  • Output:

    NO

About

No description, website, or topics provided.

Resources

Readme
Activity

Stars

0 stars

Watchers

0 watching

Forks

0 forks
Report repository

Releases

Packages

Contributors

Languages