using System;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
const int n = 10;
int[] a =new int[n] { 1, 6, 7, -51, -10, -16, 71, 53, 11, -13 };
int max = a[0];
for (int i = 1; i < n; i++)
if (a>max) max=a;
Console.WriteLine("Максимальный элемент= "+ max);
}
}
}
(С#)Нахождение третьего по величине числа массива
Имеется следующая задача:
"В массиве целых чисел (не более 100 элементов), не превосходящих по модулю 1000 и среди которых нет равных, найти порядковый номер третьего по величине числа.
Например:
Число чисел 10
1-е 1
2-е 6
3-е 7
4-е -51
5-е -10
6-е -16
7-е 71
8-е 53
9-е 11
10-е -13
Ответ: третье по величине число имеет порядковый номер 9.
Т.е. первое, самое большое число - 71, второе - 53, а третье - 11
Но как показать именно порядковый номер и как найти третье число?
Пока вот нашел только максимальный элемент.
Вообще по идее нужно написать вот так:
Но тогда выскакивает непонятное окно с ошибкой. Хотя когда я пишу:
то все нормально, и программа выбирает второй максимальный элемент.
"В массиве целых чисел (не более 100 элементов), не превосходящих по модулю 1000 и среди которых нет равных, найти порядковый номер третьего по величине числа.
Например:
Число чисел 10
1-е 1
2-е 6
3-е 7
4-е -51
5-е -10
6-е -16
7-е 71
8-е 53
9-е 11
10-е -13
Ответ: третье по величине число имеет порядковый номер 9.
Т.е. первое, самое большое число - 71, второе - 53, а третье - 11
Но как показать именно порядковый номер и как найти третье число?
Пока вот нашел только максимальный элемент.
Код:
Вообще по идее нужно написать вот так:
Код:
if (a>max) max=a[i+2];
Но тогда выскакивает непонятное окно с ошибкой. Хотя когда я пишу:
Код:
if (a>max) max=a[i+1];
то все нормально, и программа выбирает второй максимальный элемент.
Если под шарпу с ооп дают такие задачи.....
А насчет ошибки, вероятнее всего ты выходих за пределы массива(?)
+
и
не в какие рамки не лезет...
и еще...иожет цикл пересмотриш?
А насчет ошибки, вероятнее всего ты выходих за пределы массива(?)
+
Код:
if (a>max) max=a[i+2];
и
Код:
if (a>max) max=a[i+1];
не в какие рамки не лезет...
и еще...иожет цикл пересмотриш?
// n = размер массива (integer);
// k = счетчик (integer);
// ar = массив чисел (array);
// max1,max2,max3 = самый большой 1-ый, 2-ой, 3-ии числа
Язык Паскаль
// k = счетчик (integer);
// ar = массив чисел (array);
// max1,max2,max3 = самый большой 1-ый, 2-ой, 3-ии числа
Код:
Begin
max1:=ar[1];
max2:=ar[1];
max3:=ar[1];
For k:=1 to n do
If ar[k]>max1 Then max1:=ar[k];
For k:=1 to n do
If ar[k]>max2 and ar[k]<max1 Then max2:=ar[k];
For k:=1 to n do
If ar[k]>max3 and ar[k]<max2 Then max3:=ar[k];
End.
max1:=ar[1];
max2:=ar[1];
max3:=ar[1];
For k:=1 to n do
If ar[k]>max1 Then max1:=ar[k];
For k:=1 to n do
If ar[k]>max2 and ar[k]<max1 Then max2:=ar[k];
For k:=1 to n do
If ar[k]>max3 and ar[k]<max2 Then max3:=ar[k];
End.
Язык Паскаль
Попыталься что-то вроде гибрид C и PHP
Данные те же самые.
....
В Паскале прикол - массивы принято начинать в индекса 1-го ar[1];
а в РНР(Думаю и в С тоже) c 0-го индекса.
Надеюсь поможет.
Данные те же самые.
Код:
max1=ar[0];
max2=ar[1];
max3=ar[2];
for(k=0;k<n;k++){
if(ar[k]>max1) max1=ar[k];
}
for(k=0;k<n;k++){
if(ar[k]>max2 and ar[k]<max1) max2=ar[k];
}
for(k=0;k<n;k++){
if(ar[k]>max3 and ar[k]<max2) max3=ar[k];
}
max2=ar[1];
max3=ar[2];
for(k=0;k<n;k++){
if(ar[k]>max1) max1=ar[k];
}
for(k=0;k<n;k++){
if(ar[k]>max2 and ar[k]<max1) max2=ar[k];
}
for(k=0;k<n;k++){
if(ar[k]>max3 and ar[k]<max2) max3=ar[k];
}
....
В Паскале прикол - массивы принято начинать в индекса 1-го ar[1];
а в РНР(Думаю и в С тоже) c 0-го индекса.
Надеюсь поможет.
А что если пятое по величине нужно найти? или десятое??
Десять циклов, десять переменных? А что если 100 из 101?
Десять циклов, десять переменных? А что если 100 из 101?
Код:
int arr_size = 10;
int[ ] a = new int[ arr_size ] { 1, 6, 7, -51, -10, -16, 71, 53, 11, -13 };
int figure_from_top = 3;
int top_level;
int max = arr[0];
int min = arr[0];
for ( int i = 1; i < arr_size; i++ )
{
if (arr > max)
{
max = arr;
}
else if (arr < min)
{
min = arr;
}
}
int k = -1;
for ( int j = 0; j < figure_from_top - 1; j++ )
{
top_level = max;
max = min;
for ( int i = 0; i < arr_size; i++ )
{
if ( (arr < top_level) && (arr > max) )
{
max = arr;
if ( ( j + 1 ) == ( figure_from_top - 1 ) )
{
k = i;
}
}
}
}
Console.WriteLine("Индекс третьего по величине элемента: "+ string.Parse(k))
int[ ] a = new int[ arr_size ] { 1, 6, 7, -51, -10, -16, 71, 53, 11, -13 };
int figure_from_top = 3;
int top_level;
int max = arr[0];
int min = arr[0];
for ( int i = 1; i < arr_size; i++ )
{
if (arr > max)
{
max = arr;
}
else if (arr < min)
{
min = arr;
}
}
int k = -1;
for ( int j = 0; j < figure_from_top - 1; j++ )
{
top_level = max;
max = min;
for ( int i = 0; i < arr_size; i++ )
{
if ( (arr < top_level) && (arr > max) )
{
max = arr;
if ( ( j + 1 ) == ( figure_from_top - 1 ) )
{
k = i;
}
}
}
}
Console.WriteLine("Индекс третьего по величине элемента: "+ string.Parse(k))
Цитата: melon
Имеется следующая задача:
"В массиве целых чисел (не более 100 элементов), не превосходящих по модулю 1000 и среди которых нет равных, найти порядковый номер третьего по величине числа.
...
"В массиве целых чисел (не более 100 элементов), не превосходящих по модулю 1000 и среди которых нет равных, найти порядковый номер третьего по величине числа.
...
Вводим размер массива.По условию массив не задан.Не надо упрощать условие.Заполняем массив случайными числами в диапазоне от -1000 до 1000.Делаем копию массива.Сортируем массив по убыванию.
Третий по величине элемент имеет индекс 2.Ищем в копии его индекс.
Код:
...
ulong n = 0;
Console.WriteLine("Введите размер массива");
n = Convert.ToUInt64(Console.ReadLine());
Console.WriteLine("\n\tЗаполняем массив случайными цифрами от -1000 до 1000");
int[] array = new int[n];
int[] mass = new int[n];
Random r = new Random();
int length = array.Length;
Console.Write("\n");
for (int i = 0; i < length; i++)
{
array = r.Next(-1000, 1000);
mass = array;
}
Console.WriteLine("\n\tИсходный массив...\n");
foreach (int i in array)
{
Console.Write(i.ToString() + " ");
}
Console.Write("\n");
int temp = 0;
for (int j = 0; j < length; j++)
{
for (int i = 0; i < length - 1; i++)
{
if (array < array[i + 1])
{
temp = array;
array = array[i + 1];
array[i + 1] = temp;
}
}
}
Console.WriteLine("\n\tСортированный по убыванию массив...\n");
foreach (int i in array)
{
Console.Write(i.ToString() + " ");
}
int val = 2;
Console.WriteLine("\nТретье по величине число равно : "
+ array[val].ToString());
for (int i = 0; i < length; i++)
{
if (mass == array[val])
Console.WriteLine("В исходном массиве позиция : "
+ i.ToString());
}
...
ulong n = 0;
Console.WriteLine("Введите размер массива");
n = Convert.ToUInt64(Console.ReadLine());
Console.WriteLine("\n\tЗаполняем массив случайными цифрами от -1000 до 1000");
int[] array = new int[n];
int[] mass = new int[n];
Random r = new Random();
int length = array.Length;
Console.Write("\n");
for (int i = 0; i < length; i++)
{
array = r.Next(-1000, 1000);
mass = array;
}
Console.WriteLine("\n\tИсходный массив...\n");
foreach (int i in array)
{
Console.Write(i.ToString() + " ");
}
Console.Write("\n");
int temp = 0;
for (int j = 0; j < length; j++)
{
for (int i = 0; i < length - 1; i++)
{
if (array < array[i + 1])
{
temp = array;
array = array[i + 1];
array[i + 1] = temp;
}
}
}
Console.WriteLine("\n\tСортированный по убыванию массив...\n");
foreach (int i in array)
{
Console.Write(i.ToString() + " ");
}
int val = 2;
Console.WriteLine("\nТретье по величине число равно : "
+ array[val].ToString());
for (int i = 0; i < length; i++)
{
if (mass == array[val])
Console.WriteLine("В исходном массиве позиция : "
+ i.ToString());
}
...
m_Valery
опередил меня чуток, ну да ладно. кстати почему бы не использовать все возможности System.Array и не воспользоваться сначала Sort, а потом и Reverse для упорядочивания массива по убыванию?! потом для поиска в массиве элемента не воспользоваться IndexOf? плюс ко всему написанному надо еще вставить проверку на то, что числа не повторяются:
и на последок: надо вроде бы не
а
P.S. если что-то не так прошу прощения поскольку в изучение C# только начал углубляться.
опередил меня чуток, ну да ладно. кстати почему бы не использовать все возможности System.Array и не воспользоваться сначала Sort, а потом и Reverse для упорядочивания массива по убыванию?! потом для поиска в массиве элемента не воспользоваться IndexOf? плюс ко всему написанному надо еще вставить проверку на то, что числа не повторяются:
Код:
for (int j=0;j<i;j++)
if (array[j] == array)
{
i--;
break;
}
if (array[j] == array)
{
i--;
break;
}
и на последок: надо вроде бы не
Код:
array = r.Next(-1000, 1000);
а
Код:
array = r.Next(-1000, 1001);
P.S. если что-то не так прошу прощения поскольку в изучение C# только начал углубляться.
[QUOTE=;201350]m_Valery
... кстати почему бы не использовать все возможности System.Array и не воспользоваться сначала Sort, а потом и Reverse для упорядочивания массива по убыванию?! потом для поиска в массиве элемента не воспользоваться IndexOf? плюс ко всему написанному надо еще вставить проверку на то, что числа не повторяются.
...[/QUOTE]
Логично,надо использовать преимущества C#;) kosfiz,выложи,
окончательный вариант.
... кстати почему бы не использовать все возможности System.Array и не воспользоваться сначала Sort, а потом и Reverse для упорядочивания массива по убыванию?! потом для поиска в массиве элемента не воспользоваться IndexOf? плюс ко всему написанному надо еще вставить проверку на то, что числа не повторяются.
...[/QUOTE]
Логично,надо использовать преимущества C#;) kosfiz,выложи,
окончательный вариант.
вот мой вариант:
Код:
int n = 0;
int num = 0;
Random rnd = new Random();
Console.WriteLine("Введите количество элементов в массиве");
n = Convert.ToInt32(Console.ReadLine());
Console.WriteLine("Введите номер элемента");
num = Convert.ToInt32(Console.ReadLine());
int[] matrix = new int[n];
int[] temp = new int[n];
for (int i = 0; i < n; i++)
{
matrix = rnd.Next(-1000,1001);
temp = matrix;
for (int j=0;j<i;j++)
if (matrix[j] == matrix)
{
i--;
break;
}
}
Console.WriteLine("Исходный массив:");
foreach (int i in matrix)Console.WriteLine(i);
Array.Sort(temp);
Array.Reverse(temp);
Console.WriteLine("Индекс элемента:");
Console.WriteLine(Array.IndexOf(matrix,temp[num-1]));
Console.ReadKey();
int num = 0;
Random rnd = new Random();
Console.WriteLine("Введите количество элементов в массиве");
n = Convert.ToInt32(Console.ReadLine());
Console.WriteLine("Введите номер элемента");
num = Convert.ToInt32(Console.ReadLine());
int[] matrix = new int[n];
int[] temp = new int[n];
for (int i = 0; i < n; i++)
{
matrix = rnd.Next(-1000,1001);
temp = matrix;
for (int j=0;j<i;j++)
if (matrix[j] == matrix)
{
i--;
break;
}
}
Console.WriteLine("Исходный массив:");
foreach (int i in matrix)Console.WriteLine(i);
Array.Sort(temp);
Array.Reverse(temp);
Console.WriteLine("Индекс элемента:");
Console.WriteLine(Array.IndexOf(matrix,temp[num-1]));
Console.ReadKey();
Цитата: m_Valery
Сортируем массив по убыванию.
Третий по величине элемент имеет индекс 2.Ищем в копии его индекс.
Третий по величине элемент имеет индекс 2.Ищем в копии его индекс.
А почему сортировка в приведенном коде идет полностью?
Предлагается, например, сортировать по возрастанию, и сортировать, как и в приведенном коде, от начала к концу. При такой сортировке после первой итерации уже определится максимальный элемент (он будет последним в массиве), после второй итерации - второй по величине элемент, а после третьей - искомый третий по величине. Дальше сортировать нет смысла!
Код:
...
ulong n = 0;
Console.WriteLine("Введите размер массива");
n = Convert.ToUInt64(Console.ReadLine());
Console.WriteLine("\n\tЗаполняем массив случайными цифрами от -1000 до 1000");
int[] array = new int[n];
int[] mass = new int[n];
Random r = new Random();
int length = array.Length;
Console.Write("\n");
for (int i = 0; i < length; i++)
{
array = r.Next(-1000, 1000);
mass = array;
}
Console.WriteLine("\n\tИсходный массив...\n");
foreach (int i in array)
{
Console.Write(i.ToString() + " ");
}
Console.Write("\n");
int temp = 0;
for (int j = 0; j < 3; j++)
{
for (int i = 0; i < length - 1; i++)
{
if (array > array[i + 1])
{
temp = array;
array = array[i + 1];
array[i + 1] = temp;
}
}
}
Console.WriteLine("\nТретье по величине число равно : "
+ array[length-3].ToString());
for (int i = 0; i < length; i++)
{
if (mass == array[val])
Console.WriteLine("В исходном массиве позиция : "
+ i.ToString());
}
...
ulong n = 0;
Console.WriteLine("Введите размер массива");
n = Convert.ToUInt64(Console.ReadLine());
Console.WriteLine("\n\tЗаполняем массив случайными цифрами от -1000 до 1000");
int[] array = new int[n];
int[] mass = new int[n];
Random r = new Random();
int length = array.Length;
Console.Write("\n");
for (int i = 0; i < length; i++)
{
array = r.Next(-1000, 1000);
mass = array;
}
Console.WriteLine("\n\tИсходный массив...\n");
foreach (int i in array)
{
Console.Write(i.ToString() + " ");
}
Console.Write("\n");
int temp = 0;
for (int j = 0; j < 3; j++)
{
for (int i = 0; i < length - 1; i++)
{
if (array > array[i + 1])
{
temp = array;
array = array[i + 1];
array[i + 1] = temp;
}
}
}
Console.WriteLine("\nТретье по величине число равно : "
+ array[length-3].ToString());
for (int i = 0; i < length; i++)
{
if (mass == array[val])
Console.WriteLine("В исходном массиве позиция : "
+ i.ToString());
}
...
A вы уверенны, что ваша идея с дополнительным массивом и сортировкой намного эффективней? Особенно, если использовать Пузырек - помоему больше проходов по массиву будет, если сделать как говорит cheburator - лучше и приблизительно тот же эффект, что и у koltaviy. А вспомогательные массивы у нас при таких задачах как правило запрещались.
Решение koltaviy, просто немного изменила:
Решение koltaviy, просто немного изменила:
Код:
static void Main(string[] args)
{
int[ ] arr = new int[10]{ 2, 6, 7, -51, -10, -16, 71, 53, 11, -3 };
int figure_from_top = 3;
int top_level;
int max_i = 0;
int min_i = 0;
for ( int i = 1; i < arr.Length; i++ )
if (arr > arr[max_i])
max_i = i;
else if (arr < arr[min_i])
min_i = i;
for ( int j = 0; j < figure_from_top - 1; j++ )
{
top_level = arr[max_i];
max_i = min_i;
for ( int i = 0; i < arr.Length; i++ )
if ((arr < top_level) && (arr > arr[max_i]))
max_i = i;
}
Console.WriteLine("Порядковый номер третьего по величине элемента: " + (max_i+1));
}
{
int[ ] arr = new int[10]{ 2, 6, 7, -51, -10, -16, 71, 53, 11, -3 };
int figure_from_top = 3;
int top_level;
int max_i = 0;
int min_i = 0;
for ( int i = 1; i < arr.Length; i++ )
if (arr > arr[max_i])
max_i = i;
else if (arr < arr[min_i])
min_i = i;
for ( int j = 0; j < figure_from_top - 1; j++ )
{
top_level = arr[max_i];
max_i = min_i;
for ( int i = 0; i < arr.Length; i++ )
if ((arr < top_level) && (arr > arr[max_i]))
max_i = i;
}
Console.WriteLine("Порядковый номер третьего по величине элемента: " + (max_i+1));
}
можно еще проще
Код:
#define min -100
#define mas 10
#define num 3
void main()
{
int i=0, m=0, m2=0, k=0;
int m1[mas] = {1, 6, 7, -51, -10, -16, 71, 53, 11, -13};
for(m = 0; m < num; m++)
for(i = 0, m2 = min; i < mas; i++, m1[k] = min)
if( m1 > m2) m2 = m1[k = i];
cout << k << " " << m2 << endl;
}
#define mas 10
#define num 3
void main()
{
int i=0, m=0, m2=0, k=0;
int m1[mas] = {1, 6, 7, -51, -10, -16, 71, 53, 11, -13};
for(m = 0; m < num; m++)
for(i = 0, m2 = min; i < mas; i++, m1[k] = min)
if( m1 > m2) m2 = m1[k = i];
cout << k << " " << m2 << endl;
}
barracuda, интересное решение, только min помоему лучше взять -1000(по условию задачи числа не превышает тысячи по модулю) и конечно надо делать копию массива источника, а то он теряется.
А твой предыдущий вариант решения лучше удалить - оно не нужно :)
А твой предыдущий вариант решения лучше удалить - оно не нужно :)
Цитата: OlgaKr
A вы уверенны, что ваша идея с дополнительным массивом и сортировкой намного эффективней? Особенно, если использовать Пузырек - помоему больше проходов по массиву будет, если сделать как говорит cheburator - лучше и приблизительно тот же эффект, что и у koltaviy. А вспомогательные массивы у нас при таких задачах как правило запрещались.
про дополнительный массив в условии ничего не сказано, а раз ничего не сказано, то решили применить: почему нет, раз не запрещено.
далее сам автор почему-то не уделил внимания формированию массива, хотя в условии ясно сказано, что он неизвестен и кол-во элементов в нем неизвестно значит должен формироваться динамически, и существует условие о его содержимом, поэтому начали рассматривать задачу с самого начала, а не только поиск индекса.
т.к. дали ему задание реализовать на C#, то и решено было задействовать именно возможности предоставляемые этим языком программирования.
если говорить об эффективности, то для количества элементов равного 100, вопрос о том, применять тот код или иной, не имеет смысла. я проверил для 100000 элементов и могу заверить, что код m_Valery + kosfiz + cheburator выполняется за столько же времени за сколько koltaviy + OlgaKr.
причем если рассматривать оптимизацию кода написанного в совокупности m_Valery + kosfiz + cheburator, то сортировку надо проводить как написал cheburator, далее лучше не писать в цикле формирования массива
Код:
temp = matrix;
а лучше потом написать
Код:
Array.Copy(matrix, temp, matrix.Length);
далее поиск значения в массиве лучше проводить с помощью IndexOf
Код:
Array.IndexOf(matrix, val);
т.к. это работает в два раза быстрее чем подобное
Код:
for (int i = 0; i < length; i++)
{
if (mass == array[val])
Console.WriteLine("В исходном массиве позиция : "
+ i.ToString());
}
{
if (mass == array[val])
Console.WriteLine("В исходном массиве позиция : "
+ i.ToString());
}
кстати, если брать исключительно мой вариант то, тогда оттуда можно убрать
Код:
Array.Reverse(temp);
и чуть исправить код определения индекса - это съэкономит время.
про эффективность работы вроде бы все. кстати если говорить про эффектность, то код с использованием всех возможностей C# выглядит гораздо лучше, а то что не ставится временных рамок работы кода позволяет использовать как раз эти возможности.
OlgaKr В условии не сказано что масив должен сохранится
максимальное количество проходов в данном случае равна mas*num-num
минимальное - num
а вот без порчи масива
но аптимизировано для num = 3
для других num не будет работать
максимальное количество проходов в данном случае равна mas*num-num
минимальное - num
а вот без порчи масива
Код:
#define min -1000
#define mas 10
#define num 3
void main()
{
int m[mas] = {1, 6, 7, -51, -10, -16, 71, 53, 11, -13};
int i=1, k=0;
int n[num]= {min, min, min};
while(m>m[k]?n[0]=m,k=i,i=1:m>n[1]&&m<n[0]?n[1]=m,++i<mas:m>n[2]&&m<n[1]?n[2]=m,k=i,++i<mas:++i<mas);
cout << k << " - " << n[num];
}
#define mas 10
#define num 3
void main()
{
int m[mas] = {1, 6, 7, -51, -10, -16, 71, 53, 11, -13};
int i=1, k=0;
int n[num]= {min, min, min};
while(m>m[k]?n[0]=m,k=i,i=1:m>n[1]&&m<n[0]?n[1]=m,++i<mas:m>n[2]&&m<n[1]?n[2]=m,k=i,++i<mas:++i<mas);
cout << k << " - " << n[num];
}
но аптимизировано для num = 3
для других num не будет работать
выброси свой компилятор
в атаче рабочий код и рабочая прога
в атаче рабочий код и рабочая прога
Код:
using System;
using System.Collections.Generic;
using System.Text;
namespace ConsoleApplication2
{
class Program
{
static void Main(string[] args)
{
const int min = -1000;
const int max = 1000;
const int mas = 10;
const int num = 10;
long[] m = new long[mas] {1, 6, 7, -51, -10, -16, 71, 53, 11, -13};
long
i = -1,
k = -1,
r = -1,
t = -1,
s = 0;
while (s + 1 <= num)
{
long t1;
long r1;
if (t == -1) t1 = min;
else t1 = m[t];
if (r == -1) r1 = max;
else r1 = m[r];
if (i == mas && t1 < r1)
{
r = t;
k = -1;
i = -1;
s++;
}
else
{
long i1;
long k1;
long tr;
if (i == -1) i1 = min;
else i1 = m;
if (k == -1) k1 = min;
else k1 = m[k];
if (r == -1) tr = max;
else tr = m[r];
if (i1 > k1)
{
if (i1 < tr)
{
t = i;
k = i;
i = -1;
}
else
{
++i;
}
}
else
{
++i;
}
}
}
Console.WriteLine("Индекс максимального элемента= " + r + " Максимальный элемент= " + m[r]);
}
}
}
using System.Collections.Generic;
using System.Text;
namespace ConsoleApplication2
{
class Program
{
static void Main(string[] args)
{
const int min = -1000;
const int max = 1000;
const int mas = 10;
const int num = 10;
long[] m = new long[mas] {1, 6, 7, -51, -10, -16, 71, 53, 11, -13};
long
i = -1,
k = -1,
r = -1,
t = -1,
s = 0;
while (s + 1 <= num)
{
long t1;
long r1;
if (t == -1) t1 = min;
else t1 = m[t];
if (r == -1) r1 = max;
else r1 = m[r];
if (i == mas && t1 < r1)
{
r = t;
k = -1;
i = -1;
s++;
}
else
{
long i1;
long k1;
long tr;
if (i == -1) i1 = min;
else i1 = m;
if (k == -1) k1 = min;
else k1 = m[k];
if (r == -1) tr = max;
else tr = m[r];
if (i1 > k1)
{
if (i1 < tr)
{
t = i;
k = i;
i = -1;
}
else
{
++i;
}
}
else
{
++i;
}
}
}
Console.WriteLine("Индекс максимального элемента= " + r + " Максимальный элемент= " + m[r]);
}
}
}
Цитата: barracuda
Код:
using System;
using System.Collections.Generic;
using System.Text;
namespace ConsoleApplication2
{
class Program
{
static void Main(string[] args)
{
const int min = -1000;
const int max = 1000;
const int mas = 10;
const int num = 10;
long[] m = new long[mas] {1, 6, 7, -51, -10, -16, 71, 53, 11, -13};
long
i = -1,
k = -1,
r = -1,
t = -1,
s = 0;
while (s + 1 <= num)
{
long t1;
long r1;
if (t == -1) t1 = min;
else t1 = m[t];
if (r == -1) r1 = max;
else r1 = m[r];
if (i == mas && t1 < r1)
{
r = t;
k = -1;
i = -1;
s++;
}
else
{
long i1;
long k1;
long tr;
if (i == -1) i1 = min;
else i1 = m;
if (k == -1) k1 = min;
else k1 = m[k];
if (r == -1) tr = max;
else tr = m[r];
if (i1 > k1)
{
if (i1 < tr)
{
t = i;
k = i;
i = -1;
}
else
{
++i;
}
}
else
{
++i;
}
}
}
Console.WriteLine("Индекс максимального элемента= " + r + " Максимальный элемент= " + m[r]);
}
}
}
using System.Collections.Generic;
using System.Text;
namespace ConsoleApplication2
{
class Program
{
static void Main(string[] args)
{
const int min = -1000;
const int max = 1000;
const int mas = 10;
const int num = 10;
long[] m = new long[mas] {1, 6, 7, -51, -10, -16, 71, 53, 11, -13};
long
i = -1,
k = -1,
r = -1,
t = -1,
s = 0;
while (s + 1 <= num)
{
long t1;
long r1;
if (t == -1) t1 = min;
else t1 = m[t];
if (r == -1) r1 = max;
else r1 = m[r];
if (i == mas && t1 < r1)
{
r = t;
k = -1;
i = -1;
s++;
}
else
{
long i1;
long k1;
long tr;
if (i == -1) i1 = min;
else i1 = m;
if (k == -1) k1 = min;
else k1 = m[k];
if (r == -1) tr = max;
else tr = m[r];
if (i1 > k1)
{
if (i1 < tr)
{
t = i;
k = i;
i = -1;
}
else
{
++i;
}
}
else
{
++i;
}
}
}
Console.WriteLine("Индекс максимального элемента= " + r + " Максимальный элемент= " + m[r]);
}
}
}
мда. barracuda обрати внимание на результаты. ты думаешь это правильно???
а ты на num смотрел?
Цитата: barracuda
а ты на num смотрел?
так, поехали дальше.
у тебя в коде еще глюки.
1. ставлю в массиве вместо 1 1000 и num = 1. в результате вижу, что выводит 71 с индексом 6.
2. ставлю num = 10 и вмместо 1 -1000. в результате вижу то, что в аттаче.
такого быть не должно не так ли?
Цитата: kosfiz
так, поехали дальше.
у тебя в коде еще глюки.
1. ставлю в массиве вместо 1 1000 и num = 1. в результате вижу, что выводит 71 с индексом 6.
2. ставлю num = 10 и вмместо 1 -1000. в результате вижу то, что в аттаче.
такого быть не должно не так ли?
у тебя в коде еще глюки.
1. ставлю в массиве вместо 1 1000 и num = 1. в результате вижу, что выводит 71 с индексом 6.
2. ставлю num = 10 и вмместо 1 -1000. в результате вижу то, что в аттаче.
такого быть не должно не так ли?
поставь
min -1001
max 1001
Цитата: barracuda
поставь
min -1001
max 1001
min -1001
max 1001
а почему ты сразу не поставил, чтобы по условию все сразу было? или ты русского языка не разумеешь?:) ведь написано же:
[quote=melon]не превосходящих по модулю 1000[/quote]
кстати последний твой код медленноватый, какое из своих творений предложишь? а то он медленнее чем у m_Valery + kosfiz + cheburator и koltaviy + OlgaKr, причем это наблюдается уже на 10000 элементов в массиве.
Вот пришла в голову идея...
Зачем сортировать, сортировка имеет алгоритмическую сложность порядка n^2. Представленная задача практически аналогична задаче просто поиска максимального элемента. Для этого можно применить такой подход. Представьте себе обычный алгоритм поиска максимального элемента. Мы запоминаем текущий максимальный элемент, при рассмотрении очередного элемента мы сравниваем его с текущим максимумом и если данный элемент больше него, запоминаем уже данный элемент как текущий максимум. Так давайте предыдущий максимум тоже запомним, т. е. организуем список, массив и т. п., состоящий из 3 объектов (в данном случае). В качестве объектов берутся только позиции элементов в исходном массиве, т. к. значения максимума хранить нет необходимости (перед нами ведь не стоит задача выяснить значение 3-го по величине элемента, только позицию? Даже если нужно выяснить значение, можем просто обратиться к исходному массиву по этому индексу...)
Примерный код на C++ (с C# я не очень хорошо дружу, так что возлагаю переписывание кода на C# на вас; код, чесслово, не проверялся, дело было поздно ночью, точнее сказать, ранним утром, и на пивную голову, не до компилятора было):
В итоге в positions[2] имеем позицию искомого элемента. Заодно в
positions[1], positions[0] можем увидеть позицию 2-го по величине и максимального элементов.
Зачем сортировать, сортировка имеет алгоритмическую сложность порядка n^2. Представленная задача практически аналогична задаче просто поиска максимального элемента. Для этого можно применить такой подход. Представьте себе обычный алгоритм поиска максимального элемента. Мы запоминаем текущий максимальный элемент, при рассмотрении очередного элемента мы сравниваем его с текущим максимумом и если данный элемент больше него, запоминаем уже данный элемент как текущий максимум. Так давайте предыдущий максимум тоже запомним, т. е. организуем список, массив и т. п., состоящий из 3 объектов (в данном случае). В качестве объектов берутся только позиции элементов в исходном массиве, т. к. значения максимума хранить нет необходимости (перед нами ведь не стоит задача выяснить значение 3-го по величине элемента, только позицию? Даже если нужно выяснить значение, можем просто обратиться к исходному массиву по этому индексу...)
Примерный код на C++ (с C# я не очень хорошо дружу, так что возлагаю переписывание кода на C# на вас; код, чесслово, не проверялся, дело было поздно ночью, точнее сказать, ранним утром, и на пивную голову, не до компилятора было):
Код:
// Предусловие. Предполагается, что массив имеет в своем составе не менее, чем 3 различных по значению элементов.
// Ввод (или генерация) начального массива в переменную vector<int> array
...
// Конец ввода/генерации
#define MAX_VAL_NUM 3 // Определяем макрос, обозначающий, какой по величине элемент нужно искать
const size_t array_size = array.size();
size_t positions [MAX_VAL_NUM];
for (size_t i = 0; i < MAX_VAL_NUM; ++i)
positions = -1;
int current_maximum = array[0];
for (size_t i = 1; i < array_size; ++i)
{
if (array > current_maximum)
{
// Сдвиг элементов в positions
for (size_t n = MAX_VAL_NUM-1; n > 0; --n)
positions[n] = positions[n-1];
// Запоминаем текущий максимум
positions[0] = i;
current_maximum = array;
};
};
// Ввод (или генерация) начального массива в переменную vector<int> array
...
// Конец ввода/генерации
#define MAX_VAL_NUM 3 // Определяем макрос, обозначающий, какой по величине элемент нужно искать
const size_t array_size = array.size();
size_t positions [MAX_VAL_NUM];
for (size_t i = 0; i < MAX_VAL_NUM; ++i)
positions = -1;
int current_maximum = array[0];
for (size_t i = 1; i < array_size; ++i)
{
if (array > current_maximum)
{
// Сдвиг элементов в positions
for (size_t n = MAX_VAL_NUM-1; n > 0; --n)
positions[n] = positions[n-1];
// Запоминаем текущий максимум
positions[0] = i;
current_maximum = array;
};
};
В итоге в positions[2] имеем позицию искомого элемента. Заодно в
positions[1], positions[0] можем увидеть позицию 2-го по величине и максимального элементов.
Цитата: cheburator
Вот пришла в голову идея...
Зачем сортировать, сортировка имеет алгоритмическую сложность порядка n^2.
Зачем сортировать, сортировка имеет алгоритмическую сложность порядка n^2.
Ты пузырьком собираешься сортировать?
Цитата: cheburator
Представьте себе обычный алгоритм поиска максимального элемента. Мы запоминаем текущий максимальный элемент, при рассмотрении очередного элемента мы сравниваем его с текущим максимумом и если данный элемент больше него, запоминаем уже данный элемент как текущий максимум. Так давайте предыдущий максимум тоже запомним, т. е. организуем список, массив и т. п., состоящий из 3 объектов (в данном случае).
Неправильный алгоритм. Попробуй его на след. наборе данных:
{10,9,8,7,6,5}
Но движение мысли верное. Смотри:
http://forum.codenet.ru/showpost.php?p=201631&postcount=12
Цитата: Green
Но существует ещё (как минимум) один вариант: можно попробовать сортировать не исходный массив, а массив наибольших значений непосредственно при его формировании.
При этом придется сравнивать не только максимальный но и минимальный элементы этого нового массива.
Цитата: kosfiz
а почему ты сразу не поставил, чтобы по условию все сразу было? или ты русского языка не разумеешь?:) ведь написано же:
А глаза разуть? Я предложил метод, и не более.
Цитата: kosfiz
кстати последний твой код медленноватый, какое из своих творений предложишь? а то он медленнее чем у m_Valery + kosfiz + cheburator и koltaviy + OlgaKr, причем это наблюдается уже на 10000 элементов в массиве.
Это был не последний, последний я предлогал:
Код:
#define min -1000
#define max 1000
#define mas 10
#define num 9
void main()
{
long m[mas] = {1, 6, 7, -51, -10, -16, 71, 53, 11, -13};
long i=0, k=-1, r=-1, t=-1, s=0, q=0;
while(m>(k==-1?min:m[k])?m<(r==-1?max:m[r])?t=i,k=ш,++i:++i:++i,i==mas&&(t==-1?min:m[t])<(r==-1?max:m[r])?r=t,k=-1,i=0,s++,s+1<=num:s+1<=num)q++;
cout << "q=" << q << " r=" << r << " m[r]=" << m[r] << endl;
}
#define max 1000
#define mas 10
#define num 9
void main()
{
long m[mas] = {1, 6, 7, -51, -10, -16, 71, 53, 11, -13};
long i=0, k=-1, r=-1, t=-1, s=0, q=0;
while(m>(k==-1?min:m[k])?m<(r==-1?max:m[r])?t=i,k=ш,++i:++i:++i,i==mas&&(t==-1?min:m[t])<(r==-1?max:m[r])?r=t,k=-1,i=0,s++,s+1<=num:s+1<=num)q++;
cout << "q=" << q << " r=" << r << " m[r]=" << m[r] << endl;
}
Быстрей не получится, хотя
Цитата: Green
Но существует ещё (как минимум) один вариант: можно попробовать сортировать не исходный массив, а массив наибольших значений непосредственно при его формировании.
Цитата: Green
Ты пузырьком собираешься сортировать?
Я про ту сортировку, что была уже приведена здесь, в этой теме. По сути, да, пузырьком.
Цитата: Green
Ты пузырьком собираешься сортировать?
Неправильный алгоритм. Попробуй его на след. наборе данных:
{10,9,8,7,6,5}
Неправильный алгоритм. Попробуй его на след. наборе данных:
{10,9,8,7,6,5}
Действительно, глюк в алгоритме...
Глюк исправим таким образом. Массив positions инициализируем не минус едиицами, а первыми тремя различными значениями из исходного массива, подобно тому, как current_maximum инициализируется первым элементом массива. Естественно, эти три различных значения помещаются в positions в отсортированном виде. Для приведенного примера { 10, 9, 8, 7, 6, 5 } positions будет изначально содержать { 10, 9, 8 }, каковым и останется.
Насчет сравнительной сложности отчасти согласен. "Нормальная", не пузырьковая, сортировка, займет времени порядка m * log m (m - размер массива), а такой алгоритм - порядка m * n. Но насчет сравнения - не согласен: символы "О" так просто не сравниваются. Даже если n > log m (соответственно, m*n > m*log m), это еще не значит, что время будет более быстрое. К примеру, функция времени первого алгоритма - f1(m) = 100*m*log(m) + 1000 = O(m*log m); второго - 2*m*n - 3 = O(m*n). Тут даже при n > log m с большой вероятностью второй алгоритм сработает быстрее. Быстродействие можно сравнить только эмпирическим путем.
P. S.
Остается требование насчет наличия в исходном массиве хотя бы трех различных значений.
Остается требование насчет наличия в исходном массиве хотя бы трех различных значений.
Цитата: cheburator
Действительно, глюк в алгоритме...
Глюк исправим таким образом. Массив positions инициализируем не минус едиицами, а первыми тремя различными значениями из исходного массива, подобно тому, как current_maximum инициализируется первым элементом массива. Естественно, эти три различных значения помещаются в positions в отсортированном виде.
И? Что дальше?
А дальше (я ещё раз повторяю) каджый очередной элемент из исходного массива сравнивается с минимальным элементом производного массива, на основании чего происходит добавление этого элемента в производный массив и/или переход к след. элементу исходного массива.
Добавление в производный массив происходит с одновременной сортировкой и с вытеснением минимального элемента. Что в принципе можно провернуть за m*log(m), где m - размер производного массива.
Т.о. весь алгоритм работает за N*m*log(m), где N - размер исходного массива.
Цитата: cheburator
Но насчет сравнения - не согласен: символы "О" так просто не сравниваются. Даже если n > log m (соответственно, m*n > m*log m), это еще не значит, что время будет более быстрое.
"O" именно так и сравнивается, т.к. рассматривает обобщенный случай.
Пузырек тоже иногда (знаешь когда?) работает ЗНАЧИТЕЛЬНО быстрее быстрой сортировки.
Пузырек может выполниться за N, быстрая сортировка почти за N^2.
Однако ты же не будешь утверждать что нельзя сравнивать пузырьковую сортировку и быструю.
Цитата: Green
И? Что дальше?
Не совсем понятна ваша реплика.
В общем, тема исчерпана и предложено много вариантов, хороших и разных. Если критично быстродействие, остается лишь предложить совместить два алгоритма и определить эмпирическим путем, при каких числах какой алгоритм выгоднее, и выполнить ветвление на два алгоритма.
Цитата: Green
"O" именно так и сравнивается, т.к. рассматривает обобщенный случай.
Буду соблюдать приличия и стараться сильно в оффтоп не вылезать. Обсуждение сравнения функций можно вынести в отдельную тему (при желании), т. к. по моему личному опыту, далеко не все понимают, что такое органиченная функция; функция, ограниченная относительно другой функции; функция одного порядка с другой функцией. Так что
читаем учебник краткого курса матанализа Л. Д. Кудрявцева, стр. 144, п. 9.2 "Сравнение функций в окрестности заданной точки". Читаем именно матан, т. к. только он даст точный ответ, и математика играет не последнюю (точнее, главную) роль в теоретическом сравнении производительности алгоритмов.
P. S. Мне кажется, тему можно закрывать...