Романов Е.Л. Информатика и программирование. Язык Си. (конспект лекций). НГТУ. ВОПРОСЫ БЕЗ ОТВЕТОВ! - 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 сначала сортирует массив, используя двоичный алгоритм сортировки, а затем выполняет финальную проход, чтобы поменять местами пары элементов, которые были отмечены как требующие обмена.
- Важно отметить, что быстрая сортировка - это устойчивый алгоритм сортировки, что означает, что он сохраняет относительный порядок элементов с одинаковыми значениями. Однако он не является алгоритмом сортировки, который сохраняет относительный порядок элементов в целом.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д