Романов Е.Л. Информатика и программирование. Язык Си. (конспект лекций). НГТУ. ВОПРОСЫ БЕЗ ОТВЕТОВ! - 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++;
    }
}

Объяснение кода листинга программы

  1. Первый фрагмент кода реализует двоичный или линейный поиск расположения значения val в массиве out[n]. Он объявляет функцию find, которая выполняет этот поиск, а также функцию F4, которая использует find для сортировки массива in по возрастанию.
  2. Второй фрагмент кода реализует быструю сортировку массива in. Он объявляет функцию F6, которая сначала находит максимальное значение в массиве, затем выполняет быструю сортировку, используя двоичный алгоритм сортировки, и в конце устанавливает значения v0 и v1, чтобы указать на пары элементов, которые нужно поменять местами.
  3. Функция F6 использует двоичный алгоритм сортировки, который работает с битами элементов массива, а не с самими элементами. Это позволяет ей работать с массивами большего размера, чем максимальный размер int, без необходимости использовать тип данных, больший, чем int.
  4. Двоичный алгоритм сортировки работает, разделяя массив на две части: одну, где все элементы меньше опорного, и другую, где все элементы больше опорного. Затем он рекурсивно сортирует обе части.
  5. В реализации F6 используется трюк с использованием операции сдвига >>=1 для двоичного поиска, что позволяет уменьшить количество операций сдвига вдвое на каждом шаге.
  6. Функция F6 также использует трюк с использованием значения MAXINT для указания на пары элементов, которые нужно поменять местами. Это значение больше любого другого значения, которое может быть в массиве, поэтому оно гарантированно будет находиться в конце массива после сортировки.
  7. Функция F6 сначала сортирует массив, используя двоичный алгоритм сортировки, а затем выполняет финальную проход, чтобы поменять местами пары элементов, которые были отмечены как требующие обмена.
  8. Важно отметить, что быстрая сортировка - это устойчивый алгоритм сортировки, что означает, что он сохраняет относительный порядок элементов с одинаковыми значениями. Однако он не является алгоритмом сортировки, который сохраняет относительный порядок элементов в целом.

Оцени полезность:

5   голосов , оценка 3.8 из 5
Похожие ответы