очереди | java@Cat

Условие задачи:
Даны действительные числа [latex]a_{1}, \ldots, a_{n}, b_{1}, \ldots, b_{n}[/latex]. Члены последовательности [latex]c_{1}, \ldots, c_{n+1}[/latex] связаны с членами данных последовательностей соотношениями [latex]c_{n+1}=0, c_{\left (n+1\right )-i}=\frac{a_{\left (n+1\right )-i}}{b_{\left (n+1\right )-i}-c_{\left (n+1\right )-i+1}} \left (i=1, \ldots, n \right ).[/latex] Получить [latex]c_{1}, \ldots, c_{n+1}[/latex].

Входные данные:
В первой строке задано число [latex]n[/latex]. В последующих строках записано две числовые последовательности из n чисел.

Выходные данные:
Вывести результирующую последовательность [latex]c[/latex], найденную согласно условию задачи.

Тесты:

Входные данные		Выходные данные
28	100 23 45 62 17 873 46 927 64 5 8 9 3 0 89 73 12 53 62 7 12 35 64 50 227 23 100 80 12 34 23 6 7 8 9 25 10 9 73 24 27 8 4 3 2 0 9 1 45 62 100 104 5 6 14 21	8.89145197864941 0.7532429753739995 3.46536409638595 10.014351523139867 -0.19111480725820545 95.9517680178081 -1.0983211464949347 50.88210356032888 6.781413598577088 0.5624396639914702 0.11015755091584475 0.3767441860465116 0.1111111111111111 0.0 4.803215151847447 -14.529255339679752 8.024345590557227 0.5045509487875016 -105.04390117066583 9.590229411789153 0.2700904535823736 0.5704400476332376 0.6438589905891021 0.5993533748082496 20.57676071984004 -6.031862745098037 9.813084112149534 3.8095238095238093 0.0
10	2 -4 1 2 45.2 34 -23 34 56 7.09 -3.4 4 4 -5 2.4 34.04 23 567 -3 4	-0.8567913942992066 -1.0657095142326265 0.24663198875517678 -0.05462407795229777 31.61389033873605 0.9702487256173882 -1.0025608427005548 0.05874893533055214 -11.733892090099529 1.7725 0.0

Код программы:

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n=in.nextInt();
		double[] A = new double[n];
		double[] B = new double[n];
		double[] C = new double[n+1];
		String ans = new String("");
		double inf = 1.0 / 0;
		C[n] = 0.0;
		int k=0;
		while(k<n){
			A[k] = in.nextDouble();
			k++;
		}
		String c=in.nextLine();
		int t=0;
		while(t<n){
			B[t]=in.nextDouble();
			t++;
		}
		for (int i=1; i<=n; i++){
			if(B[n-i]-C[n-i+1]!=0) C[n-i]=A[n-i]/(B[n-i]-C[n-i+1]);
			else C[n-i]=inf;
		}
		for (int i=0; i<=n; i++){
			ans+=Double.toString(C[i])+" ";	
		}
		System.out.println(ans);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

int n=in.nextInt();

double[] A = new double[n];

double[] B = new double[n];

double[] C = new double[n+1];

String ans = new String("");

double inf = 1.0 / 0;

C[n] = 0.0;

int k=0;

while(k<n){

A[k] = in.nextDouble();

k++;

}

String c=in.nextLine();

int t=0;

while(t<n){

B[t]=in.nextDouble();

t++;

}

for (int i=1; i<=n; i++){

if(B[n-i]-C[n-i+1]!=0) C[n-i]=A[n-i]/(B[n-i]-C[n-i+1]);

else C[n-i]=inf;

}

for (int i=0; i<=n; i++){

ans+=Double.toString(C[i])+" ";

}

System.out.println(ans);

}

Алгоритм решения:
Узнаем количество необходимых элементов: считаем число [latex]n[/latex]. С помощью двух циклов также считаем все элементы массивов [latex]a[/latex] и [latex]b[/latex]. Заведем еще один счетчик для нахождения значений ячеек нового массива, воспользовавшись нашей заданной формулой [latex]c_{\left (n+1\right )-i}=\frac{a_{\left (n+1\right )-i}}{b_{\left (n+1\right )-i}-c_{\left (n+1\right )-i+1}} \left (i=1, \ldots, n \right )[/latex] при условии, что [latex]c_{n+1}=0.[/latex] Выведем все элементы единой строкой.

Код программы на Java
Условие задачи

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

Ссылка на задачу с сайта e-olymp

Ваш друг проводит научные исследования по проблеме Конского Минимального Путешествия (КМП), которая состоит в том, чтобы найти кратчайший замкнутый тур ходов конём, который посещает каждую клетку заданного набора из [latex]n[/latex] клеток на шахматной доске ровно один раз. Он считает, что самая трудная часть задачи состоит в определении наименьшего числа ходов для перемещения коня между двумя заданными клетками и что, как только вы поможете ему решить эту подзадачу, то ему решить всю задачу будет намного легче.

Вы, конечно, знаете, что дело обстоит как раз наоборот. Таким образом, вы в свою очередь решили предложить ему самому написать программу, которая решает «трудную» часть.

Ваша задача состоит в том, чтобы написать программу, которая принимает координаты двух клеток [latex]n[/latex] и [latex]b[/latex] в качестве входных данных, а затем определяет количество ходов конем кратчайшим путём из [latex]a[/latex] в [latex]b[/latex].

Входные данные:

Входные данные будут содержать один или более тестов. Каждый тест состоит из одной строки, содержащей координаты двух клеток, разделенные одним пробелом. Координаты клетки являются двумя символами, первый из которых буква ([latex]a[/latex]—[latex]h[/latex]), задающая столбец и второй – цифра ([latex]1[/latex]—[latex]8[/latex]), задающая строку на шахматной доске.

Выходные данные:

Для каждого теста вывести одну строку следующего содержания: «Путь от xx к yy занимает n шагов»

Тест

Пример входных данных	Пример выходных данных
[latex]e2[/latex] [latex]e4[/latex]	Путь от [latex]e2[/latex] к [latex]e4[/latex] занимает [latex]2[/latex] шагов.
[latex]a1[/latex] [latex]b2[/latex]	Путь от [latex]a1[/latex] к [latex]b2[/latex] занимает [latex]4[/latex] шагов.
[latex]b2[/latex] [latex]c3[/latex]	Путь от [latex]b2[/latex] к [latex]c3[/latex] занимает [latex]2[/latex] шагов.
[latex]a1[/latex] [latex]h8[/latex]	Путь от [latex]a1[/latex] к [latex]h8[/latex] занимает [latex]6[/latex] шагов.
[latex]a1[/latex] [latex]h7[/latex]	Путь от [latex]a1[/latex] к [latex]h7[/latex] занимает [latex]5[/latex] шагов.
[latex]h8[/latex] [latex]a1[/latex]	Путь от [latex]h8[/latex] к [latex]a1[/latex] занимает [latex]6[/latex] шагов.
[latex]b1[/latex] [latex]c3[/latex]	Путь от [latex]b1[/latex] к [latex]c3[/latex] занимает [latex]1[/latex] шагов.
[latex]f6[/latex] f[latex]6[/latex]	Путь от [latex]f6[/latex] к [latex]f6[/latex] занимает [latex]0[/latex] шагов.

Решение

import java.util.*;
import java.lang.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

class Main {

    public static class Pair <T1, T2> {
        public T1 fst;
        public T2 snd;

        public Pair(T1 t1, T2 t2) {

            this.fst = t1;
            this.snd = t2;
        }
    }

    public static void main(String[] args) 
 {
        char a, b;
        int nx, ny, tx, ty;
        int mx[] = {-1, -1, 1, 1, -2, -2, 2, 2};
        int my[] = {2, -2, 2, -2, 1, -1, 1, -1};
        int A[][] = new int[8][8];
        Scanner s = new Scanner(System.in);
        String str;
        while (s.hasNextLine()) {
            String line = s.nextLine();
            Pattern p = Pattern.compile("^(.)(\\d) (.)(\\d)$");
            Matcher m = p.matcher(line);
            m.find();
            a = m.group(1).toCharArray()[0];
            ny = Integer.parseInt(m.group(2));
            b = m.group(3).toCharArray()[0];
            ty = Integer.parseInt(m.group(4));
            nx = a - 'a';
            ny--;
            tx = b - 'a';
            ty--;
            A[nx][ny] = 0;
            Queue<Pair<Integer, Integer>> q = new LinkedList<Pair<Integer, Integer>>();
            q.add(new Pair<Integer, Integer>(nx, ny));
            while (!q.isEmpty()) {
                Pair<Integer, Integer> c = q.peek();
                int x = c.fst, y = c.snd;
                if (x == tx && y == ty) break;
                q.remove();
                for (int i = 0; i < 8; i++) {
                    if (x + mx[i] >= 0 && x + mx[i] < 8 && y + my[i] >= 0 && y + my[i] < 8) {
                        q.add(new Pair<Integer, Integer>(x + mx[i], y + my[i]));
                        A[x + mx[i]][y + my[i]] = A[x][y] + 1;
                    }
                }
            }
            System.out.printf("To get from %c%d to %c%d takes %d knight moves.\n", a, ny + 1, b, ty + 1, A[tx][ty]);
        }
    }
}

import java.util.*;

import java.lang.*;

import java.util.regex.Matcher;

import java.util.regex.Pattern;

class Main {

public static class Pair <T1, T2> {

public T1 fst;

public T2 snd;

public Pair(T1 t1, T2 t2) {

this.fst = t1;

this.snd = t2;

}

public static void main(String[] args)

{

char a, b;

int nx, ny, tx, ty;

int mx[] = {-1, -1, 1, 1, -2, -2, 2, 2};

int my[] = {2, -2, 2, -2, 1, -1, 1, -1};

int A[][] = new int[8][8];

Scanner s = new Scanner(System.in);

String str;

while (s.hasNextLine()) {

String line = s.nextLine();

Pattern p = Pattern.compile("^(.)(\\d) (.)(\\d)$");

Matcher m = p.matcher(line);

m.find();

a = m.group(1).toCharArray()[0];

ny = Integer.parseInt(m.group(2));

b = m.group(3).toCharArray()[0];

ty = Integer.parseInt(m.group(4));

nx = a - 'a';

ny--;

tx = b - 'a';

ty--;

A[nx][ny] = 0;

Queue<Pair<Integer, Integer>> q = new LinkedList<Pair<Integer, Integer>>();

q.add(new Pair<Integer, Integer>(nx, ny));

while (!q.isEmpty()) {

Pair<Integer, Integer> c = q.peek();

int x = c.fst, y = c.snd;

if (x == tx && y == ty) break;

q.remove();

for (int i = 0; i < 8; i++) {

if (x + mx[i] >= 0 && x + mx[i] < 8 && y + my[i] >= 0 && y + my[i] < 8) {

q.add(new Pair<Integer, Integer>(x + mx[i], y + my[i]));

A[x + mx[i]][y + my[i]] = A[x][y] + 1;

}

System.out.printf("To get from %c%d to %c%d takes %d knight moves.\n", a, ny + 1, b, ty + 1, A[tx][ty]);

}

Ссылка на решение задания с сайта e-olymp

Ссылка на решение задания на онлайн компиляторе Ideone.com

Описание решения

Для начала объявим переменные aи b типа char, где a и b — это координаты двух клеток. В цикле при помощи форматированного ввода по шаблону вводим 4 переменных, в которых a, ny — координата одной клетки и b, ty — координата другой клетки. nx — цифровая координата, которую мы получаем из буквы, отнимая от a. Создаем очередь, добавляем начальную клетку и ищем все возможные ходы пока не попадем в нужную клетку. Чтобы получить длину пути, нужно хранить длины путей до данной клетки в матрице и обновлять ее, по ходу продвижения. Длина в начальной клетке — 0, а длина в каждой последующей — 1. На экран выводим количество шагов, которые необходимо сделать конем, чтобы попасть из одной клетки в другую.

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

Tag Archives: очереди

A281 Последовательные вычисления значений нового массива

e-olymp 2820. Перемещение коня