Другие языки программирования и технологии
Помогите пожалуйста составить решение с задачей по программированию(на любом языке программирования)
Чарльз Ф. Мантц изучает животный мир саванн. Ни в одном уголке Земли нет такого изобилия крупных животных, к ак в африканских саваннах. Бесчисленные стада антилоп, зебр, буйволов, слонов, жирафов кочуют на просторах саванн, переходя с одного пастбища на другое или в поисках водопоев. У исследователя есть спутниковые снимки участка саванны и он хочет определить количество кочующих по нему стад животных. Напишите программу, которая вычисляет количество стад по результатам анализа снимков. Известно, что животные из одного стада не отходят друг от друга более чем на расстояние D и держатся от животных из другого стада на расстоянии более D. В первой строке ввода содержится два целых числа, разделенных пробелом – количество животных N (1 ≤ N ≤ 1000) и расстояние D (1 ≤ D ≤ 100). Далее следует N строк, в каждой строке содержатся два целых числа Xi, Yi (0 ≤ Xi, Yi ≤ 1000) – координаты i-го животного. Вывести одно целое число – количество стад. Пример ввода: 4 2 1 1 2 2 3 3 10 1 Пример вывода 2
Задача похожа на олимпиадную. А если вы - олимпиадник, то разберётесь в реализации на любом языке, не так ли?
Код на Nemerle:
using System;
using System.IO;
using Nemerle.Utility;
struct Vector
{
public X : double;
public Y : double;
public this (x : double, y : double)
{
X = x;
Y = y;
}
public static @-(minuend : Vector, substrahend : Vector) : Vector
{
Vector(minuend.X - substrahend.X, minuend.Y - substrahend.Y);
}
public Length : double
{
get
{
def sqr(x)
{
x * x;
}
def sqrt(x)
{
Math.Sqrt(x);
}
sqrt(sqr(X) + sqr(Y));
}
}
public override ToString() : string
{
$"($X, $Y)";
}
}
class Animal
{
_location : Vector;
public this(x : int, y : int)
{
_location = Vector(x, y);
}
public GetDistance(from : Animal) : double
{
(_location - from._location).Length;
}
public override ToString() : string
{
_location.ToString();
}
}
namespace Herds
{
module Program
{
ReadData(filename : string) : int * list[int * int]
{
def file = File.OpenRead(filename);
using (def reader = StreamReader(file))
{
def get_next_pair()
{
def line = reader.ReadLine();
def words = line.Split(array[' ', '\t']);
def parse(word)
{
int.Parse(word);
}
def a = parse(words[0]);
def b = parse(words[1]);
(a, b);
}
def (n, d) = get_next_pair();
def get_locations(i = 0, acc = [])
{
if (i < n)
{
def location = get_next_pair();
get_locations(i + 1, location :: acc);
}
else
acc.Reverse();
}
(d, get_locations());
}
}
Main() : void
{
def exclude(animals : list[Animal], center, max_distance)
{
animals.FoldLeft(
(0, []),
fun (animal : Animal, acc)
{
def (count, rest) = acc;
def distance = animal.GetDistance(center);
if (distance <= max_distance)
(count + 1, rest);
else
(count, animal :: rest);
}
);
}
def exclude_next_herd(animals, max_distance)
{
def (_, excluded_animals) = animals.FoldLeft(
(0, []),
fun (center, acc)
{
def (herd_animals_count, excluded_animals) =
exclude(animals, center, max_distance);
def (count, _) = acc;
if (herd_animals_count > count)
(herd_animals_count, excluded_animals);
else
acc;
}
);
excluded_animals;
}
def get_count(animals, max_distance)
{
def loop(animals, max_distance, count)
{
match (animals)
{
| [] => count;
| _ =>
def excluded_animals =
exclude_next_herd(animals, max_distance);
loop(excluded_animals, max_distance, count + 1);
}
}
loop(animals, max_distance, 0);
}
def print_locatons(animals)
{
Console.WriteLine("Locations are:");
animals.Iter(animal => Console.WriteLine(animal));
}
def print_result(count)
{
Console.WriteLine($"Heards count is $count");
}
def (d, locations) = ReadData("input.txt");
def animals = locations.Map(location => Animal(location));
def count = get_count(animals, d);
print_locatons(animals);
print_result(count);
}
}
}
1. Запрашиваем максимальное расстояние и координаты зверей.
2. Для каждого зверя находим количество попавших в стадо, центром которого является выбранный, зверей и список зверей, не попавших в стадо.
3. Находим зверей, не попавших в стадо с максимальным количеством зверей.
4. Применяем 2 для зверей из 3.
Код на Nemerle:
using System;
using System.IO;
using Nemerle.Utility;
struct Vector
{
public X : double;
public Y : double;
public this (x : double, y : double)
{
X = x;
Y = y;
}
public static @-(minuend : Vector, substrahend : Vector) : Vector
{
Vector(minuend.X - substrahend.X, minuend.Y - substrahend.Y);
}
public Length : double
{
get
{
def sqr(x)
{
x * x;
}
def sqrt(x)
{
Math.Sqrt(x);
}
sqrt(sqr(X) + sqr(Y));
}
}
public override ToString() : string
{
$"($X, $Y)";
}
}
class Animal
{
_location : Vector;
public this(x : int, y : int)
{
_location = Vector(x, y);
}
public GetDistance(from : Animal) : double
{
(_location - from._location).Length;
}
public override ToString() : string
{
_location.ToString();
}
}
namespace Herds
{
module Program
{
ReadData(filename : string) : int * list[int * int]
{
def file = File.OpenRead(filename);
using (def reader = StreamReader(file))
{
def get_next_pair()
{
def line = reader.ReadLine();
def words = line.Split(array[' ', '\t']);
def parse(word)
{
int.Parse(word);
}
def a = parse(words[0]);
def b = parse(words[1]);
(a, b);
}
def (n, d) = get_next_pair();
def get_locations(i = 0, acc = [])
{
if (i < n)
{
def location = get_next_pair();
get_locations(i + 1, location :: acc);
}
else
acc.Reverse();
}
(d, get_locations());
}
}
Main() : void
{
def exclude(animals : list[Animal], center, max_distance)
{
animals.FoldLeft(
(0, []),
fun (animal : Animal, acc)
{
def (count, rest) = acc;
def distance = animal.GetDistance(center);
if (distance <= max_distance)
(count + 1, rest);
else
(count, animal :: rest);
}
);
}
def exclude_next_herd(animals, max_distance)
{
def (_, excluded_animals) = animals.FoldLeft(
(0, []),
fun (center, acc)
{
def (herd_animals_count, excluded_animals) =
exclude(animals, center, max_distance);
def (count, _) = acc;
if (herd_animals_count > count)
(herd_animals_count, excluded_animals);
else
acc;
}
);
excluded_animals;
}
def get_count(animals, max_distance)
{
def loop(animals, max_distance, count)
{
match (animals)
{
| [] => count;
| _ =>
def excluded_animals =
exclude_next_herd(animals, max_distance);
loop(excluded_animals, max_distance, count + 1);
}
}
loop(animals, max_distance, 0);
}
def print_locatons(animals)
{
Console.WriteLine("Locations are:");
animals.Iter(animal => Console.WriteLine(animal));
}
def print_result(count)
{
Console.WriteLine($"Heards count is $count");
}
def (d, locations) = ReadData("input.txt");
def animals = locations.Map(location => Animal(location));
def count = get_count(animals, d);
print_locatons(animals);
print_result(count);
}
}
}
1. Запрашиваем максимальное расстояние и координаты зверей.
2. Для каждого зверя находим количество попавших в стадо, центром которого является выбранный, зверей и список зверей, не попавших в стадо.
3. Находим зверей, не попавших в стадо с максимальным количеством зверей.
4. Применяем 2 для зверей из 3.
ну и чё сложного!
нужно сделать матрицу А [1...x, 1..y], что бы в каждую строку ввести номера животных для каждого стада, а по y будет количество стад. Далее делам цикл и берем первый элемент и сравниваем со всеми остальными элементами, если расстояние меньше D то заносим в первую строку (первое стадо) номер животного после окончания этого цикла начинаем новый цикл по количеству элементов в первой строке А, и проверяем с остальными элементами соответственно исключая элементы которые уже в массиве А. По окончанию цикла определим всех животных с первого стада. Ну и остальные стада можно вычислить по такому же принципу, ну уже исключая животные с первого стада.
Похожие вопросы
- помогите пожалуйста, я запуталась в задаче..((по программированию в С++
- Помогите с программированием. Составить решения для задачи С++.
- Помогите пожалуйста найти ошибку в задаче (Язык программирования Си)
- Зачем нужен решение математические задачи в программировании
- Посоветуйте сайт для решения сложных задач по программированию, тоесть хочу научится решать сложные задачи, что читать?
- Хватит ли знаний школьной математики для решения большинства задач по программированию?
- Помогите, пожалуйста, с решением задачи из задачника Абрамяна.
- Помогите пожалуйста оптимизировать решение задачи (Зайчик) на C++
- Помогите пожалуйста составить программы для следующих задач:
- Помогите пожалуйста с решением задач в паскале