Заметили ошибку ?
Выделите это место и нажмите Ctrl + Q

Треугольные числа на C# (Олимпиадная задача по информатике)



Здравствуйте! Сегодня разберём олимпиадную задачу по информатике, которая называется треугольные числа.


Задача треугольные числа.

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


Треугольные числа - олимпиадная задача по информатике

Помогите Никите по заданному количеству камешков N найти наибольшую сторону правильного треугольника, который из них можно сложить. Например, если у Никиты 30 камешков, то длина наибольшей стороны правильного треугольника, который из них можно сложить, будет 7.


Задача по информатике - треугольные числа

Тесты для самопроверки:

30 7
29 7
28 7
27 6
9876543210000 4444443

Решение:

Рассмотрим треугольные числа. Видим, что первое треугольное число - это просто 1. Второе число - это сумма чисел до 2 (1+2), третье число - сумма чисел до 3 (1+2+3) и т.д.


Зависимость треугольных чисел

Плюс ко всему, второе число образует треугольник со стороной 2, третье число со стороной 3 и т.д.


Рассмотрим треугольное число по номером n. Видим, что это сумма арифметической прогрессии.


Арифметическая прогрессия в треугольных числах

Свернём по формуле арифметической прогрессии. Число Sn (сумма арифметической прогрессии) в нашей задаче это количество камней, которое вводит пользователь. Число n в данном уравнении обозначает порядковый номер треугольного числа или длину стороны правильного треугольника, который можно составить из данного количества камней.


Остаётся решить данное уравнение относительно n в целых числах, чтобы разгадать нашу задачу.


Квадратное уравнение в треугольных числах

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


Запрограммируем данную задачу на C#


using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Numerics;

namespace ConsoleApp15
{
    class Program
    {
        static void Main(string[] args)
        {
            ulong n, a;

            a = Convert.ToUInt64(Console.ReadLine());

            n = (ulong)(Math.Sqrt(1 + 8 * a)  - 1) / 2;

            Console.WriteLine(n);

            Console.ReadKey();
        }
    }
}

Данное решение удовлетворяет всем приведённым в условии задачи тестам. Если тесты выходят за диапазон типа данных ulong, то можно использовать тип данных BigInteger, и вместо Math.Sqrt, тогда придётся писать отдельную функцию для извлечения корня, например, методом бинома Ньютона.


На этом всё, до свидания!





09-01-2020 в 22:13:42





Похожая статья:

Пишем программу для решения задания номер 14 ОГЭ по информатике на PHP

Всем привет! Вчера, как Вы знаете, вышел видеоурок по подготовке 14 за...

Категория: Алгоритмы  Подкатегория: Задачи
Дата: 15-01-2018 в 16:47:34 0



Оставить коментарий:



Напишите email, чтобы получать сообщения о новых комментариях (необязательно):


Задача против робота. Расположите картинки горизонтально:


Последние
видео:



ЕГЭ по информатике - Задание 17
ЕГЭ по информатике - Задание 16





Давайте
дружить!


Группа Вконтакте Code-Enjoy

Твиттер Александра Калужского

YouTube канал Code-Enjoy