Closest number, C++

Pavletka 0 Точки

Closest number, C++

Условието на задачата: Write a program which finds the two closest (by value) integer numbers in an array and prints the absolute difference between them.

Input:

1 105 10 100 3

Output:

2 (The closest numbers are 1 and 3, abs(1,3) = 2)

Това е начинът, по който мисля, че трябва да се реши задачата:

int n;
cin>>n;

int arr[n];
int i;
for (i=0; i<n; i++)
{
cin>>arr[i];
}

int k = INT_MAX;
int m;

for(i=0; i<n; i++)
{
m = abs(arr[i], arr[i+1]);
if (m < k)
{
k = m;
}
cout<<endl;
cout<<k<<endl;
}

Може ли някой да ми помогне, защото явно това не е правилният код. Благодаря Ви!

Тагове:

29/11/2018 21:50:38 C++ Programming

willystyle 2472 Точки

Имаш предвид, че алгоритъма не ти е верен може би. Така обхождаш масива веднъж и сравняваш разлика между съседни елементи. Това е добро, ако масива е сортиран. Ако не е сортиран, може да направиш още един вложен цикъл и да сравниш m = abs(arr[i], arr[j]); .Но все пак със сортировка мисля, че сложността на алгоритъма е по-малка.

int n;
cin>>n;

int arr[n];
int i;
for (i=0; i<n; i++)
{
cin>>arr[i];
}

sort(arr, arr + n);

int k = INT_MAX;
int m; int indexMin = 0;

for(i=0; i<n - 1; i++)
{
m = abs(arr[i], arr[i+1]);
if (m < k)
{
k = m; indexMin = i;
}
}

cout<<endl;
cout<<k<<endl;

cout<<arr[indexMin ]<<endl;

cout<<arr[indexMin + 1]<<endl;

29/11/2018 22:31:01 29/11/2018 22:47:51

kolioi 641 Точки

Това няма да работи, ако n=1, т.е. ако имаме само едно число. Точно това е уловката в тази задача. Миналата седмица един колега беше пуснал тема за това. Аз съм го направил така

int min_diff = 0;
if (n > 1)
{
	min_diff = abs(arr[0] - arr[1]);
	for (int i = 0; i < n; ++i)
		for (int j = i + 1; j < n; ++j)
			if (abs(arr[i] - arr[j]) < min_diff)
				min_diff = abs(arr[i] - arr[j]);
}
cout << min_diff;

30/11/2018 00:01:34

willystyle 2472 Точки

Единствено ми прави впечетление, дали i не трябва да върти до n - 1 ? Но това ще спести само 4 операции, със същия резултат от кода :)

30/11/2018 00:26:26

kolioi 641 Точки

Твоят код работи добре за повече числа. Обаче при n=1 джадж очаква 0 (това не го пише в условието на задачата), а твоят изход е INT_MAX. Един от тестовете е такъв и затова някои хора вземат само 80/100.

П.П. А моя код е на ниво Софтюни :)

30/11/2018 05:17:43 30/11/2018 05:23:06

Покажи всички коментари