A324. Делители одного числа, взаимно простые с другим

07/07/2017 by Халафов Нурал

Задача

Даны целые числа [latex]p[/latex] и [latex]q[/latex]. Получить все делители числа [latex]q[/latex], взаимно простые с числом [latex]p[/latex].

Тесты

q	p	Все делители числа q, взаимно простые с числом p
40	15	1 2 4 8
87	3	1 29

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

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static long gcd(long x, long y){
		return (y != 0) ? gcd(y, x%y) : x;
	}
	public static void main (String[] args) 
	{
		int q = 0, p;
		Scanner in = new Scanner(System.in);
		q = in.nextInt();
		p = in.nextInt();
		for (int i = 1; i <= q; i++)
		{ 
        	if((q % i) == 0) {
            	if (gcd(i,p) == 1)
                	System.out.println(i + " ");
        	}
    	}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Ideone

{

public static long gcd(long x, long y){

return (y != 0) ? gcd(y, x%y) : x;

}

public static void main (String[] args)

{

int q = 0, p;

Scanner in = new Scanner(System.in);

q = in.nextInt();

p = in.nextInt();

for (int i = 1; i <= q; i++)

{

if((q % i) == 0) {

if (gcd(i,p) == 1)

System.out.println(i + " ");

}

Решение

Воспользуемся рекурсивной реализацией алгоритма Евклида. Пусть m и n — не равные нулю целые неотрицательные числа, и пусть [latex]m\geq n[/latex]. Тогда, если [latex]n=0[/latex], [latex]GCD(n,m)=m[/latex], а если [latex]n\neq 0[/latex], то для чисел [latex]m,n[/latex] и [latex]k[/latex], где [latex]k[/latex], где [latex]k[/latex] — остаток от деления [latex]m[/latex] и [latex]n[/latex], выполняется равенство [latex]GCD(m,n)=GCD(n,k)[/latex].

Для нахождения делителей числа [latex]q[/latex] взаимно простых с [latex]p[/latex], программа проверяет остатки от деления [latex]q[/latex] на все числа [latex]i[/latex] от [latex]1[/latex] до [latex]q[/latex]. Если остаток равен нулю, то число [latex]i[/latex] является делителем [latex]q[/latex]. Для каждого такого числа выполняется поиск наибольшего общего делителя (НОД — Greatest common divisor, GCD) [latex]i[/latex] и [latex]p[/latex] по алгоритму Евклида. [latex]1[/latex], то числа [latex]i[/latex] и [latex]p[/latex] взаимно простые.

e-olymp 906

06/07/2017 by Болдин Валерий

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

Найдите сумму цифр в десятичной записи целого числа.

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

Целое десятичное число — [latex]x[/latex].

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

Сумма цифр десятичного числа — [latex]sum[/latex].

Тесты

№	Входные данные	Выходные данные
1	234	9
2	489	21
3	31	4

Решение:

class ThirdLab
{
	public static void main (String[] args)
	{
		int x;
		int sum = 0;
		Scanner input = new Scanner(System.in);
		x = input.nextInt();
		while((x%10)>0){
		sum+= x%10;	
		x/=10;
		}
		System.out.println(sum);
	}
}

class ThirdLab

{

public static void main (String[] args)

{

int x;

int sum = 0;

Scanner input = new Scanner(System.in);

x = input.nextInt();

while((x%10)>0){

sum+= x%10;

x/=10;

}

System.out.println(sum);

}

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

Объявляем две переменные типа int — x и sum . Вводим с клавиатуры целое десятичное число x . Используя цикл while добавляем в sum остаток от деления x на 10 до тех пор, пока остаток от деления не станет равным нулю. Выводим значение sum на экран с помощью функции System.out.println() .

e-olymp 7365

03/07/2017 by Присяжный Михаил

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

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

Ученикам первого класса дополнительно дают стакан молока и пирожок, если вес первоклассника менее 30 кг. В первых классах школы учится [latex]n[/latex] учеников. Стакан молока имеет емкость 200 мл, а упаковки молока – 0.9 л. Определить количество дополнительных пакетов молока и пирожков, необходимых каждый день.

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

Количество учеников [latex]n[/latex] и их веса

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

Количество пирожков и пакетов молока

Тесты

№	Кол-во учеников	Вес учеников	Кол-во пирожков	Кол-во пакетов молока
1	3	23 24 25	3	1
2	6	11 15 26 27 22 30	5	1
3	7	21 30 30 27 21 22 30	4	1

Решение

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

class Main {
    public static void main(String[] args) {

        Scanner s = new Scanner(System.in);
        int p = 0; 
        int n, k; 
        double m, u, w;
        n = s.nextInt();
        m = 0.2;
        u = 0.9;
        for (int i = 0; i < n; i++) {
            w = s.nextDouble();
            if (w < 30) p++;
        }
        k = (int) Math.ceil(p * m / u);
        System.out.println(k + " " + p);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main {

public static void main(String[] args) {

Scanner s = new Scanner(System.in);

int p = 0;

int n, k;

double m, u, w;

n = s.nextInt();

m = 0.2;

u = 0.9;

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

w = s.nextDouble();

if (w < 30) p++;

}

k = (int) Math.ceil(p * m / u);

System.out.println(k + " " + p);

}

Ссылка на решение с e-olymp

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

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

Для начала объявим переменные типа int для учеников n и пирожков p и упаковок молока k. Для определения количества дополнительных пакетов молока и пирожков, используем цикл for, в котором, проверяем, присутствуют ли в наших учениках те, вес которых ниже 30 кг weight<30. Если вес ученика ниже 30 кг weight<30, то даем ему пирожок p++ и прибавляем 200 мл молока. На экран выводим количество пирожков и количество пакетов молока для заданного количества учеников с заданным весом.

A334(а). Вложенная сумма

30/06/2017 by Хоба Юрий

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

Вычислить: [latex]\sum \limits_{i=1}^{m}\sum \limits_{j=1}^{n}\frac{1}{i+j^2}[/latex], где [latex]m[/latex] и [latex]n[/latex] — вводимые числа.

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

[latex]m[/latex] и [latex]n[/latex] — верхние границы сумм.

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

Результат вычисления выражения.

Тесты

№	Входные данные	Выходные данные
1	1 5	0.8972
2	19 3	5.3469
3	164 395	34.7509
4	0 102	0

Результаты тестов на wolframalpha.com:

Решение

import java.util.*;

class Task3
{
	public static void main (String[] args)
	{
		int m, n;
		double S = 0;
		Scanner in = new Scanner(System.in);
		m = in.nextInt();
		n = in.nextInt();
		for (int i = 1; i <= m; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				S += 1.0/(i + j*j);
			}
		}
		
		System.out.println(S);
	}
}

import java.util.*;

class Task3

{

public static void main (String[] args)

{

int m, n;

double S = 0;

Scanner in = new Scanner(System.in);

m = in.nextInt();

n = in.nextInt();

for (int i = 1; i <= m; i++)

{

for (int j = 1; j <= n; j++)

{

S += 1.0/(i + j*j);

}

System.out.println(S);

}

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

Так как необходимо найти вложенную сумму, будем использовать вложенный цикл (цикл внутри цикла). На каждом шаге внутреннего цикла прибавляем к сумме (которая изначально равна 0) результат выражения [latex]1/(i + j^2)[/latex]. В числителе вместо 1 пишем 1.0, что преобразует результат выражения в тип double, так как результат выражения — число вещественное.

Посмотреть, как работает программа со входными данными 164 395 можно на сайте ideone.

Ю 4.9

30/06/2017 by Шостак Дмитрий

Задача

В матрице [latex]A(n, m) [/latex] все ненулевые элементы заменить обратными по величине и противоположными по знаку.

Тесты

№	n	m	Входная матрица	Выходная матрица
1	3	3	6 -2 -1 0 0 4 11 2 -3	-0.167 0.500 1.000 0.000 0.000 -0.250 -0.091 -0.500 0.333
2	3	4	-3 -9 15 12 -31 -8 2 8 -1 2 -6 -8	0.333 0.111 -0.067 -0.083 0.032 0.125 -0.500 -0.125 1.000 -0.500 0.167 0.125
3	4	3	1 1 1 1 1 1 1 1 1 1 1 1	-1.000 -1.000 -1.000 -1.000 -1.000 -1.000 -1.000 -1.000 -1.000 -1.000 -1.000 -1.000

Решение

class FifthLab
{
	public static void main (String[] args)
	{
		Scanner input = new Scanner(System.in);
		int n, m;
		
		n = input.nextInt();
		m = input.nextInt();
		
		double[][] A = new double[n][m];
		
		for(int i = 0; i < n; i++)
		{
			for(int j = 0; j < m; j++)
			{
				A[i][j] = input.nextDouble();
			}
		}
		
		for(int i = 0; i < n; i++)
		{
			for(int j = 0; j < m; j++)
			{
				if(A[i][j] != 0)
				{
					A[i][j] = -(1/A[i][j]);
				}
			}
		}
		
		for(int i = 0; i < n; i++)
		{
			for(int j = 0; j < m; j++)
			{
				System.out.printf("%.3f ",A[i][j]);
			}
			System.out.println();
		}
	}
}

class FifthLab

{

public static void main (String[] args)

{

Scanner input = new Scanner(System.in);

int n, m;

n = input.nextInt();

m = input.nextInt();

double[][] A = new double[n][m];

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

{

for(int j = 0; j < m; j++)

{

A[i][j] = input.nextDouble();

}

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

{

for(int j = 0; j < m; j++)

{

if(A[i][j] != 0)

{

A[i][j] = -(1/A[i][j]);

}

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

{

for(int j = 0; j < m; j++)

{

System.out.printf("%.3f ",A[i][j]);

}

System.out.println();

}

Проверить работу кода можно в облаке по ссылке — Ideone.

Пояснения

Объявляем и инициализируем переменные n и m , которые являются размерами нашей матрицы [latex]A[/latex]. Объявляем нашу матрицу и создаем экземпляр с размерами [latex]n[/latex] x [latex]m[/latex]. Далее создаем цикл по i от 0 до [latex]n-1[/latex] в котором создаем вложенный цикл по j от 0 до [latex]m-1[/latex], и в нем поэлементно вводим значения матрицы. В следующем цикле снова создаем вложенный, в котором мы проходим по каждому элементу матрицы и проверяем не равен ли он нулю if(A[i][j] != 0) . Если условие выполняется, то мы заменяем элемент на обратный и меняем знак. В последнем цикле выводим полученную матрицу, элементы которой будут выводится с точностью до трех символов после запятой.

А320. Вложенный цикл

29/06/2017 by Шостак Дмитрий

Задача

Вычислить [latex] \sum\limits_{k = 1}^n (k^3 \sum\limits_{l = 1}^m (k-l)^2) [/latex] при произвольных целых [latex]n[/latex] и [latex]m[/latex].

Тесты

Тесты были подготовлены и проверены с помощью ресурса WolframAlpha.

№	n	m	Результат
1	3	2	144
2	2	9	1332
3	4	4	1120

Решение

class ThirdAndHalfLab
{
	public static void main (String[] args)
	{
		Scanner input = new Scanner(System.in);
		int n, m, k, l;
		n = input.nextInt();
		m = input.nextInt();
		long m_sum = 0, n_sum = 0;
		
		for(k = 1; k <= n; k++)
		{
			for(l = 1; l <= m; l++)
			{
				m_sum += (k-l)*(k-l);
			}
			n_sum += k*k*k * m_sum;
			m_sum -= m_sum;		
		}
		System.out.println(n_sum);
	}
}

class ThirdAndHalfLab

{

public static void main (String[] args)

{

Scanner input = new Scanner(System.in);

int n, m, k, l;

n = input.nextInt();

m = input.nextInt();

long m_sum = 0, n_sum = 0;

for(k = 1; k <= n; k++)

{

for(l = 1; l <= m; l++)

{

m_sum += (k-l)*(k-l);

}

n_sum += k*k*k * m_sum;

m_sum -= m_sum;

}

System.out.println(n_sum);

}

Проверить работу кода можно в облаке по ссылке — Ideone.

Пояснения

Объявляем и инициализируем переменные n и m из потока ввода. Объявляем переменные для сумм: m_sum для вложенного цикла по [latex]l[/latex] и n_sum для цикла по [latex]k[/latex]. Далее создаем цикл по [latex]k[/latex] от 1 до [latex]n[/latex], в котором мы создаем вложенный цикл по [latex]l[/latex] от 1 до [latex]m[/latex], в котором вычисляем [latex]\sum\limits_{l=1}^m (k-l)^2[/latex] в переменную m_sum , по выходу из данного цикла добавляем произведение [latex] k^3 * \sum\limits_{l = 1}^m (k-l)^2 [/latex] в переменную n_sum , после чего обнуляем переменную m_sum . По выходу из цикла выводим финальную сумму в консоль.

А116г

29/06/2017 by Шостак Дмитрий

Задача

Даны натуральное число [latex]n[/latex] и действительное число [latex]x[/latex]. Вычислить [latex]\prod\limits_{k = 1}^n (1+\frac{\sin(kx)}{k!})[/latex].

Тесты

№	n	x	Произведение
1	4	3.22	0.9673
2	11	214.3	2.8177
3	1	14	1.9906
4	7	0.76	2.8456

Решение

class ThirdLab
{
	public static void main (String[] args)
	{
		Scanner input = new Scanner(System.in);
		double x, mult = 1;
		int n, k, fact = 1;
		
		n = input.nextInt();
		x = input.nextDouble();
		
		for(k = 1; k <= n; k++)
		{
			fact *= k;
			mult *= 1 + (Math.sin(k*x)/fact);
		}
		
		System.out.printf("%.4f", mult);
	}
}

class ThirdLab

{

public static void main (String[] args)

{

Scanner input = new Scanner(System.in);

double x, mult = 1;

int n, k, fact = 1;

n = input.nextInt();

x = input.nextDouble();

for(k = 1; k <= n; k++)

{

fact *= k;

mult *= 1 + (Math.sin(k*x)/fact);

}

System.out.printf("%.4f", mult);

}

Проверить работу кода можно в облаке по ссылке — Ideone.

Пояснения

Для вычисления данного в условии произведения кроме действительного x и натурального n введем такие переменные: mult — переменная произведения для вычисления в цикле, fact — переменная факториала [latex]k[/latex].

Инициализируем переменные n и x значениями из потока ввода, после чего создаем цикл по [latex]k[/latex] от 1 до [latex]n[/latex], в котором будет вычисляться факториал и, собственно, само произведение. При вычислении произведения используем функцию sin() стандартной библиотеки Math. По завершению цикла, выводим произведение с точностью до четырёх символов после запятой.

А694а. Многомерные массивы

28/05/2017 by Anh Tuan

Условие
Получить квадратную матрицу порядка $latex \begin{pmatrix}1 &0 &\cdots & 0 \\ 0 & 1 &\cdots &0 \\ \cdots &\cdots &\cdots \cdots & \cdots \\ 0 & 0 & \cdots & 1\end{pmatrix}$

Тесты

n	Матрица
3	1 0 0 0 1 0 0 0 1
4	1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1
6	1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1

import java.util.Scanner;
public class Lab6
{
    public static void main(String[] args) 
    {
        int n;
        Scanner scanIn = new Scanner(System.in);        
        n = scanIn.nextInt();
        int[][] m = new int[n][n];
        for(int i = 0; i < n; i++)
        {
            m[i][i] = 1;
        }
        for(int i = 0; i < n; i++) 
        {
            for(int y = 0; y < n; y++) 
            {
                System.out.println(m[i][y] + " ");
            }
            System.out.println("\n");
        }
    }   
}

import java.util.Scanner;

public class Lab6

{

public static void main(String[] args)

{

int n;

Scanner scanIn = new Scanner(System.in);

n = scanIn.nextInt();

int[][] m = new int[n][n];

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

{

m[i][i] = 1;

}

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

{

for(int y = 0; y < n; y++)

{

System.out.println(m[i][y] + " ");

}

System.out.println("\n");

}

Решение

С помощью цикла заполняем главную диагональ единицами.
Приравниваем элементы не равные единице к нулю.
Вывод массива.

Iseone.com

MLoop 15. Циклические вычисления

28/05/2017 by Anh Tuan

Условие
Вычислите с точностью значение функции $latex f(x)=\csc x$. При вычислениях допустимо использовать только арифметические операции.

x	$latex \varepsilon$	Результат
42	0.3	-8.09848e-05
8	0.15	-0.0117188
55.5	0.04	-3.50972e-055
-12	0.6	0.00347222
-82	0.0001	-3.23677e-08

package lab3; 
import java.util.Scanner;
public class Lab3 
{ 
    public static void main(String[] args) 
    {
        Scanner scanIn = new Scanner(System.in);
        double x, e; 
        x = scanIn.nextDouble(); 
        e = scanIn.nextDouble();
        double sum1 = x; // в случае, когда  i=0
        double sum2 = -x * x * x / 6; // в случае, когда i=1
        for (int i = 2; Math.abs(1 / sum2 - 1 / sum1) >= e; i++) 
        {
            sum1 = sum2;
            sum2 *= -x * x / ((2 * i) * (2 * i + 1)); 
        }

        System.out.println("1 / sum2: " + 1 / sum2);
    }
}

package lab3;

import java.util.Scanner;

public class Lab3

{

public static void main(String[] args)

{

Scanner scanIn = new Scanner(System.in);

double x, e;

x = scanIn.nextDouble();

e = scanIn.nextDouble();

double sum1 = x; // в случае, когда i=0

double sum2 = -x * x * x / 6; // в случае, когда i=1

for (int i = 2; Math.abs(1 / sum2 - 1 / sum1) >= e; i++)

{

sum1 = sum2;

sum2 *= -x * x / ((2 * i) * (2 * i + 1));

}

System.out.println("1 / sum2: " + 1 / sum2);

}

Решение
Косеканс — это тригонометрическая функция, которою можно определить формулой $latex \csc x=\frac{1}{\sin x}$

. Таким образом, мы можем разложить функцию

в бесконечную сумму степенных функций, воспользовавшись формулой Тейлора. Получим, что $latex \sin x=x-\frac{{x}^{3}}{3!}+\frac{{x}^{5}}{5!}-\dots=\sum_{n=0}^{\propto}\frac{{-1}^{n}\times{x}^{2n+1}}{\left(2n+1\right)!}$

. Слагаемые данной суммы являются геометрической прогрессией, знаменатель который можно найти по формуле $latex \frac{a_n}{a_{n-1}}=\frac{\frac{{-1}^{n}\times{a}^{2n+1}}{\left(2n+1 \right)!}}{\frac{{-1}^{n-1}\times{a}^{2n-1}}{\left(2n-1 \right)!}}=\frac{\left( -1\right){a}^{2}}{2n\times\left( 2n+1\right)}$

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

-го и

-го слагаемых будет больше заданной точности.

Ideone.com

A410e

16/10/2016 by Эдуард Брагар

Дана целочисленная матрица [latex]\begin{bmatrix}a_{i,j}\end{bmatrix},i,j=1,..,n[/latex].Получить [latex]b_{1},..,b_{n}[/latex],где [latex]b_{i}[/latex] — это:

[latex]\underset{1\leq j\leq n}{\max a_{ij}}\ * \underset{1\leq j\leq n}{\min a_{ji}}[/latex]

Исходя из задачи ясно, что из данной матрицы надо взять максимальный элемент [latex]i[/latex]-й строки и умножить его на минимальный элемент [latex]i[/latex] -го столбца. Так например, если нам дана матрица 2-го порядка [latex]\begin{Vmatrix}1&2\\4&1\end{Vmatrix}[/latex] то [latex]b_{1} = 2[/latex], [latex]b_{2} = 4[/latex].

    import java.util.*;
    import java.lang.*;
    import java.io.*;
     
    /* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception{
		Scanner in = new Scanner(System.in);
		int n,maxa,mina;
		n = in.nextInt();
		int a[][] = new int[n][n];
		
		for(int i = 0 ; i < n; ++i){
			for(int j = 0; j < n; ++j) {
				a[i][j] = in.nextInt();
			}
		}
		
		int b[] = new int[n];
		
		for( int i = 0; i < n; ++i ) {
		
			maxa = a[i][0]; //Придаем максимуму значение первого элемента i-й строки.
			mina = a[0][i]; //Минимуму же придаем значение первого элемента i-го столбца.
		
			for( int j = 0; j < n; ++j ) {
				maxa = (maxa > a[i][j] ? maxa : a[i][j]); //Вычисляем максимум i-й строки.
				mina = (mina < a[j][i] ? mina : a[j][i]); //Минимум i-го столбца.
			}
		
			b[i] = maxa * mina; //Наш результат.
		}	
			
		for( int i = 0; i < n; ++i ){
			System.out.print( b[i] + " " );
		}	
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Ideone

{

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

Scanner in = new Scanner(System.in);

int n,maxa,mina;

n = in.nextInt();

int a[][] = new int[n][n];

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

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

a[i][j] = in.nextInt();

}

int b[] = new int[n];

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

maxa = a[i][0]; //Придаем максимуму значение первого элемента i-й строки.

mina = a[0][i]; //Минимуму же придаем значение первого элемента i-го столбца.

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

maxa = (maxa > a[i][j] ? maxa : a[i][j]); //Вычисляем максимум i-й строки.

mina = (mina < a[j][i] ? mina : a[j][i]); //Минимум i-го столбца.

}

b[i] = maxa * mina; //Наш результат.

}

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

System.out.print( b[i] + " " );

}

Тесты

Матрица порядка [latex]n[/latex], где [latex]n[/latex]:	[latex]a[i][j][/latex]	Результат
2	[latex]\begin{Vmatrix}1&2\\4&1\end{Vmatrix}[/latex]	2 4
3	[latex]\begin{Vmatrix}1&2&3\\4&1&-6\\1&-2&-1\end{Vmatrix}[/latex]	3 -8 -6

Решение

Для нахождения максимума [latex]a_{ij}[/latex], введем переменную и будем придавать ей начальное значение 1-го элемента [latex]i[/latex]-й строки. Дабы при расчете максимума проходя по элементам строки мы не сравнивали каждый [latex]i[/latex]-й элемент с 1-м, придавать начальное значение максимуму мы будем в цикле по [latex]i[/latex]. Аналогично с минимумом [latex]a_{ij}[/latex], одно единственное но, начальное значение минимума будет равно первому элементу [latex]i[/latex]-го столбца.

http://ideone.com

java@Cat

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

Tag Archives: циклы

A324. Делители одного числа, взаимно простые с другим

e-olymp 906

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

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

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

Тесты

Решение:

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

e-olymp 7365

A334(а). Вложенная сумма

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

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

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

Тесты

Решение

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

Ю 4.9

Задача

Тесты

Решение

Пояснения

А320. Вложенный цикл

Задача

Тесты

Решение

А116г

Задача

Тесты

Решение

Пояснения

А694а. Многомерные массивы

MLoop 15. Циклические вычисления

A410e

Тесты

Решение