Романов Е.Л. Информатика и программирование. Язык Си. (конспект лекций). НГТУ. ВОПРОСЫ БЕЗ ОТВЕТОВ! - C (СИ)
Формулировка задачи:
Добрый день!
Есть ли у кого ответы на "вопросы без ответов" которые даны в учебнике (Романов Е.Л. Практикум по программированию на C++.Уч. пособие. БХВ.2004.pdf) и лекциях (Романов Е.Л. Информатика и программирование. Язык Си.)??? Конкретно интересуют 3 и 7 вопрос в следующих главах (это если по лекциям):3.2. Немного арифметики
Содержательно сформулировать результат выполнения функции, примерно в таком виде: "Функция находит в массиве минимальный элемент и возвращает в качестве результата его индекс"://------------------------------------------------ 3
int F3(int c[], int n)
{ int i,j;
for (i=0; i<n-1; i++)
for (j=i+1; j<n; j++)
if (c[i]==c[j]) return i;
return -1; }
//------------------------------------------------ 7
int F7(int c[], int n)
{ int i,j,m,s;
for (s=0, i=0; i < n-1; i++)
{
for (j=i+1, m=0; j<n; j++)
if (c[i]==c[j]) m++;
if (m > s) s = m;
}
return s; }3.3.Итерационные процессы и циклы
Определить общий вид степенного ряда, вычисляемого в данной функции.//-----------------------------------------------3
for (s=0, sn = x; n=1; fabs(sn) > eps; n+=2)
{ s += sn;
sn= sn * x * x / (n*(n+1));
}
//-----------------------------------------------7
for (s=0, sn = x, n=1; fabs(sn) > eps; n++)
{ s += sn;
sn= sn * x * x * (2*n-1) / (2*n+1);
}
[B]3.4. Символы, строки, тексты[/B]
//------------------------------------------------- 3
void F3(char c[])
{ int i;
for (i=0; c[i] !='\0'; i++)
if (c[i] >='a' && c[i] <='z')
c[i] += 'A' - 'a';
}
//------------------------------------------------- 7
int F7(char c[])
{ int i,s;
for (i=0; c[i] !='\0'; i++)
if (c[i] >='0' && c[i]<='7') break;
for (s=0; c[i] >='0' && c[i] <='7'; i++)
s = s * 8 + c[i] - '0';
return s; }3.5. Сортировка и поиск
По тексту программы определите алгоритм сортировки.void F3(int in[],int n)
{ int a,b,dd,i,lasta,lastb,swap;
for (a=lasta=0, b=lastb=n, dd=1; a < b;
dd = !dd, a=lasta, b=lastb)
{
if (dd)
{
for (i=a,lastb=a; i<b; i++)
if (in[i] > in[i+1])
{ lastb = i;
swap = in[i]; in[i]=in[i+1]; in[i+1]=swap;
}
}
else
{
for (i=b,lasta=b; i>a; i--)
if (in[i-1] > in[i])
{ lasta = i;
swap = in[i]; in[i]=in[i-1]; in[i-1]=swap;
} } } }
//--------------------------------------------------7
void F7(int A[], int n)
{
int i,found;
do { found =0;
for (i=0; i<n-1; i++)
if (A[i] > A[i+1])
{ int cc; cc = A[i]; A[i]=A[i+1]; A[i+1]=cc;
found++;
}
} while(found !=0);
}Решение задачи: «Романов Е.Л. Информатика и программирование. Язык Си. (конспект лекций). НГТУ. ВОПРОСЫ БЕЗ ОТВЕТОВ!»
textual
Листинг программы
//------------------------------------------------- 4
int find(int out[],int n, int val);
// Двоичный или линейный поиск расположения значения val
// в массиве out[n]
void F4(in,n)
int in[],n;
{
int i,j,k;
for (i=1; i<n; i++)
{ int c; c = in[i]; k = find(in,i,c);
for (j=i; j!=k; j--) in[j] = in[j-1];
in[k] = c; }
}
//------------------------------------------------- 6
#define MAXINT 0x7FFF
void F6(int in[], int n, int v0[], int v1[])
{
int m,i,max,i0,i1;
for (i=0, max=0; i<n; i++)
if (in[i] > max) max=in[i];
for (m=1; m <=max; m <<=1);
for (m >>=1; m !=0; m >>=1)
{
for (i0=i1=0; i0+i1 < n; )
if ((in[i0+i1] & m) ==0)
v0[i0] = in[i0+i1], i0++;
else
v1[i1] = in[i0+i1], i1++;
v0[i0] = v1[i1] = MAXINT;
for (i0=i1=0; i0+i1 < n; )
if (v0[i0] < v1[i1])
in[i0+i1] = v0[i0], i0++;
else
in[i0+i1] = v1[i1], i1++;
}
}
Объяснение кода листинга программы
- Первый фрагмент кода реализует двоичный или линейный поиск расположения значения val в массиве out[n]. Он объявляет функцию find, которая выполняет этот поиск, а также функцию F4, которая использует find для сортировки массива in по возрастанию.
- Второй фрагмент кода реализует быструю сортировку массива in. Он объявляет функцию F6, которая сначала находит максимальное значение в массиве, затем выполняет быструю сортировку, используя двоичный алгоритм сортировки, и в конце устанавливает значения v0 и v1, чтобы указать на пары элементов, которые нужно поменять местами.
- Функция F6 использует двоичный алгоритм сортировки, который работает с битами элементов массива, а не с самими элементами. Это позволяет ей работать с массивами большего размера, чем максимальный размер int, без необходимости использовать тип данных, больший, чем int.
- Двоичный алгоритм сортировки работает, разделяя массив на две части: одну, где все элементы меньше опорного, и другую, где все элементы больше опорного. Затем он рекурсивно сортирует обе части.
- В реализации F6 используется трюк с использованием операции сдвига
>>=1для двоичного поиска, что позволяет уменьшить количество операций сдвига вдвое на каждом шаге. - Функция F6 также использует трюк с использованием значения MAXINT для указания на пары элементов, которые нужно поменять местами. Это значение больше любого другого значения, которое может быть в массиве, поэтому оно гарантированно будет находиться в конце массива после сортировки.
- Функция F6 сначала сортирует массив, используя двоичный алгоритм сортировки, а затем выполняет финальную проход, чтобы поменять местами пары элементов, которые были отмечены как требующие обмена.
- Важно отметить, что быстрая сортировка - это устойчивый алгоритм сортировки, что означает, что он сохраняет относительный порядок элементов с одинаковыми значениями. Однако он не является алгоритмом сортировки, который сохраняет относительный порядок элементов в целом.