Наведемо деякі приклади розв'язання задач

1. Розглянемо алгоритм сортування методом "бульбашки". Розсортируємо літери в рядку у порядку зростання їх кодів. Причому розглянемо два варіанти програми: із застосуванням операції індексації до елементів рядка та без нього, лише через покажчики. Ідея сортування методом "бульбашки" досить проста. Розглядаючи масив зліва направо, перевіряємо, чи менший перший елемент за наступний. Якщо ця умова виконується, то розглядається другий елемент масиву і т. д. Якщо ж виявиться, що поточний елемент більший за наступний, то ці елементи міняються місцями, і перегляд масиву починається спочатку. Перший варіант програми: #define YES 1#define NO 0 bsort(char *s) { register int i; /*індекс літери, що порівнюється*/ register int need=YES; /*чи потрібно продовжувати сортування*/ while(need){ need=NO; /*не потрібно*/ for(i=0; s[i+1]; i++) /*умова циклу: ми порівнюємо i-ту та i+1-шу літери, *тому перевіряємо наявність i+1-ї літери*/ if(s[i]>s[i+1]){/*у неправильному порядку*/ swap(&s[i], &s[i+1]); /*переставити*/ need=YES; /*щось змінилось: потрібно *повторити перегляд масиву літер*/ } } } Другий варіант програми: bpsort(char *s){ register char *p; register need=YES; while(need){ need=NO; for(p=s; p[1]!='\0'; p++) if(*p>*(p+1)){ swap(p, p+1); need=YES; } }} /*обмін двох літер, що знаходяться за адресами s1 і s2*/swap(s1, s2) register char *s1, *s2;{ char tmp; /*temporary*/ tmp=*s1; *s1=*s2; *s2=tmp;} char sample1[]="Homo homini lupus est – ergo bibamus!";char sample2[sizeof(sample1)]; /*масив такого самого обсягу*/main(){ strcpy(sample2, sample1); /*скопіювати*/ bsort (sample1); printf("%s\n", sample1); bpsort(sample2); printf("%s\n", sample2);} Специфікацію пам'яті register у даному прикладі використано з метою збільшення швидкодії програми, що не принципово. Слід звернути увагу на використання функції swap ().

2. Переформатуємо матрицю так, щоб її стовпчики розміщувались за спаданням їх поелементних сум.

Матрицю запишемо в динамічному масиві. При цьому слід звернути увагу на специфіку виділення пам'яті за допомогою функції malloc:

sum=(int *)malloc(m*sizeof(int));arr=(int *)malloc(n*m*sizeof(int));

При такому виділенні пам'ять має бути коректно звільнена за допомогою функції free():

free(sum);free(arr);

Текст програми:

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
void main()
{int i,j,k,n,m,t,*sum,*arr;
clrscr();
puts("Введи n");

scanf("%d%d",&n,&m);
sum=(int *)malloc(m*sizeof(int));
arr=(int *)malloc(n*m*sizeof(int));
for(i=0;i<n;i++)
for(printf("\n"),j=0;j<m;j++)
{*(arr+i*m+j)=rand()%21;printf("%4d",*(arr+i*m+j));}
printf("\n\n");
for(j=0;j<m;j++)
{for(i=0,sum[j]=0;i<n;i++) sum[j]+=*(arr+i*m+j);
printf("%4d",sum[j]);
}
for(i=1;i<m;i++)
for(j=0;j<m-i;j++)
{if(sum[j]>=sum[j+1]) continue;
t=sum[j];sum[j]=sum[j+1];sum[j+1]=t;
for(k=0;k<n;k++)
{t=*(arr+k*m+j);*(arr+k*m+j)=*(arr+k*m+j+1);*(arr+k*m+j+1)=t;}
}
printf("\n\n");
for(i=0;i<n;i++)
for(printf("\n"),j=0;j<m;j++)
printf("%4d",*(arr+i*m+j));
printf("\n\n");
for(j=0;j<m;j++) printf("%4d",sum[j]);

free(sum);free(arr);
getch();
}

3. Нехай у масиві записано деякий текст. Обчислимо середню кількість слів у реченні та середню довжину речення:

#include <stdio.h>
#include <conio.h>
#include <string.h>
void main()
{
char text[128], //вихідний текст
copy[128], //копія вихідного тексту
*p, //початок чергового речення
*s, //початок чергового слова
raz1[]="!?.", //роздільники речень
raz2[]=".?!,;: ";//роздільники слів
intl, //довжина тексту
k, //кількість речень
u;
do
{
clrscr();
puts("Введіть вхідний текст");
gets(text);
l=strlen(text);
strcpy(copy,text);
for(p=strtok(text,raz1),k=0;p!=NULL;p=sttok(NULL,raz1))
k++;
for(s=strtok(copy,raz2),u=0;s!=NULL;s=strtok(NULL,raz2))
u++;
puts("Середня довжина речень:");
printf("%5d",l/k);
puts("\nСередня кількість слів у реченні");
printf("%5d",u/k);
puts("\nДля продовження натисніть ENTER, для виходу – ESC");
}while(getch()!=27);
}

4. Нехай задано цілочисельний арифметичний вираз, записаний як рядок у десятковій системі числення. Перевіримо правильність його запису й обчислимо значення. Вираз записано без дужок, операції виконуються в порядку їх наступності.

#include <stdio.h>
#include <string.h>
#include <conio.h>
#include <stdlib.h>

void main()
{
char a_v[80], a_v1[80], *p, c[40];
char *oper="+-*/%", *cifr="0123456789", *c_o="0123456789+-*/%";
int a[40], l_a_v, l, i, j, jk, ac; textmode(1);
textcolor(YELLOW);
textbackground(BLUE);
m1:clrscr();
puts("Введіть арифметичний вираз: ");
gets(a_v);
strcpy(a_v1, a_v);
l_a_v=strlen(a_v);
l=strspn(a_v,c_o);
if(l!=l_a_v) {puts("\n Помилка у виразі"); goto end;}
p=strtok(a_v, oper);
i=0;
do
{
a[i++]=atoi(p);
}
while(p=strtok(NULL, oper));
strcpy(a_v, a_v1);
p=strtok(a_v, cifr);
j=0;
do
{
c[j++]=*p;
}
while(p=strtok(NULL, cifr));
if(i!=j+1) {puts("\n Помилка у виразі"); goto end;}
jk=j;
ac=a[0];
i=j=0;
while(j<jk)
{
switch(c[j++])
{
case '+': ac+=a[++i]; break;
case '-': ac-=a[++i]; break;
case '*': ac*=a[++i]; break;
case '/': ac/=a[++i]; break;
case '%': ac%=a[++i];
}
}
strcpy(a_v, a_v1);
printf("\n%s=%d", a_v, ac);
end:
printf("\n\n Для продовження натисніть 7:");
scanf("%d", &l); getchar();
if(l==7) goto m1;}

5. Зашифруємо текст методом Гронсфельда. Ключем у цьому методі є скінченна послідовність цифр, яку записують підряд над символами тексту, що шифрується так: замість кожної літери у вихідному тексті друкується символ, віддалений від цієї літери (у вибраній системі кодування, напр., ascii) на величину відповідного елемента ключа, що стоїть над цією літерою.

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
void main()
{
int n,*arr,i;
char str[301],ch;

srand(time(NULL));
m1:
clrscr();
printf("Введіть текст(не більше 300 символів), що закінчується <Enter>:\n");
gets(str);
n=strlen(str);

arr=NULL;
arr=(int*) calloc(n,sizeof(int));//виділення пам’яті

clrscr();

puts("Введений текст:");
printf("\"%s\"",str);

putchar('\n');
puts("\nСформований ключ:");
for(i=0;i<n;i++)
{
/*заповнення масиву випадковими числами з діапазону [0...99] та друк*/
arr[i]=rand()%100;
printf("%4d",arr[i]);
}

for(i=0;i<n;i++) str[i]-=arr[i];
printf("\n\nЗашифрований текст:\n");
putchar('"');
for(i=0;i<n;i++) printf("%c",str[i]);
putchar('"');

puts("\n\nРозшифровка:");
putchar('"');
for(i=0;i<n;i++) printf("%c",str[i]+arr[i]);
putchar('"');

free(arr); //очищення пам’яті
printf("\n\nПродовжуємо? (7 - так):");
if(getch()=='7') goto m1;
}

6. Відцентруємо рядки тексту. Вхідні рядки не мають містити табуляцій.

#include <stdio.h>extern char *gets();#define WIDTH 60 /*ширина аркуша*/main(){ char rd[81]; register char *s; char *head, /*початок тексту*/ *tail; /*кінець тексту*/ register int len, i; int shift; /*відступ*/ /*Читати зі стандартного введення в rd по одному рядку, * доки файл не закінчиться.*/ while(gets(rd)!=NULL){ if(!*rd){ /*Рядок порожній*/ putchar('\n'); continue; } /*пропуск пропусків на початку рядка*/ for(s=rd; *s==' '; s++); if(! *s){ /*Рядок складається лише з пропусків*/ putchar('\n'); continue; } head=s; /*стати на кінець рядка*/ while(*s) s++; /*шукати останній непропуск*/ s--; while(*s==' ' && s!=rd) s--; tail=s; /*Довжина тексту*/ len=(tail-head)+1; /*різниця покажчиків – ціле число*/ shift=(WIDTH–len)/2; if(shift<0){ fprintf(stderr, "Рядок довший ніж %d\n", WIDTH); shift=0; } /*Друк результату*/ for(i=0; i<shift; i++) putchar(' '); while(head<=tail) putchar(*head++); putchar('\n'); }}7. Задача про розмін монети. Знайдемо всі можливі коефіцієнти a0...an розкладання числа S у вигляді S=a0*c0+a1*c1+... +an*cn, де c0...cn задані та впорядковані, ai>=0, ci>=0.#include <stdio.h>/*Тут задаємо вартості розмінних монет*/int cost[]={ 1, 2, 3, 5, 10, 15, 20, 50, 100, 300, 500 /*копійок*/}; #define N (sizeof cost/sizeof(int))int count[N]; /*кількість монет даного типу (коефіцієнти ai)*/long nvar; /*кількість варіантів*/ main(ac, av) char *av[];{ int coin; if(ac==1){ fprintf(stderr, "Укажіть, яку монету розмінювати: %s число\n", av[0]); exit(1); } coin=atoi(av[1]); printf("Таблиця розмінів монети %d к.\n", coin);printf("Кожний стовпчик містить кількість монет указаної вартості. \n");printf("----------------------------------------------------\n");printf("|5р.|3р.|1р.|50к.|20к.|15к.|10к.|5к.|3к.|2к.|1к.|\n");printf("----------------------------------------------------\n"); change(N-1, coin); printf("----------------------------------------------------\n"); printf("Усього %ld варіантів\n", nvar);} /*рекурсивний розмін*/change(maxcoin, sum) int sum; /*монета, яку міняємо*/ int maxcoin; /*індекс по масиву cost[] монети максимальної вартості, допустимої при даному розміні.*/{ register i; if(sum==0){/*уся сума розміняна*/ /*роздрукувати черговий варіант*/ putchar('|'); for(i=N-1; i>=0;i--) if(count[i]) printf("%3d |", count[i]); else printf("|"); putchar('\n'); nvar++; return; } if(sum>=cost [maxcoin]){ /*якщо можна видати монету вартістю cost[maxcoin], то відати її:*/ count[maxcoin]++; /*порахували видану монету*/ /*розмінюємо залишок суми: Перший аргумент – можливо, можна дати ще одну таку монету? Другий аргумент – загальна сума зменшилась на одну монету cost[maxcoin].*/ change(maxcoin, sum – cost[maxcoin]); count[maxcoin] --; /*... Тепер спробуємо інший варіант...*/ } /*спробувати розмін дрібнішими монетами*/ if(maxcoin) change(maxcoin-1, sum);}

8. Множення n -вимірних матриць. Розглянемо способи зображення множення багатовимірних матриць і визначення їх добутку. Відоме множення звичайних прямокутних чи квадратних матриць за правилом "рядок на стовпчик". Звернемося до тривимірних матриць А та B, елементи яких можна записати у тривимірні масиви. Розглядаючи процес множення за аналогією з двовимірними матрицями, можемо зобразити тривимірну матрицю А як вектор-стовпчик двовимірних:

A = ; B = .

Аналогічно матрицю B можна уявити як вектор-рядок двовимірних матриць. Тоді результатом множення є конструкція

C = || ||, , де .

Тут є звичайним множенням квадратних матриць і, отже, двовимірною матрицею. З погляду зображення даних результат множення тривимірних матриць є чотиривимірною матрицею та зображується чотиривимірним масивом. За рекурсією можемо визначити добуток довільних n -вимірних матриць A та B, розглядаючи їх відповідно як вектор-стовпчик і вектор-рядок n -1-вимірних матриць:

С = A * B, C = || ||, ,

( – n -1-вимірні матриці). Тоді добутком n -вимірних матриць буде n + 2-вимірна матриця (n > = 4).

Виходячи зі способу розміщення в пам'яті n -вимірних масивів у С, дотримуватимемося такої самої домовленості, записуючи n -вимірні масиви в динамічному одновимірному. При цьому вважатимемо, що для довільної n -вимірної матриці А, яка зображується як вектор-стовпчик n -1-вимірних матриць A ₁, A ₂, … A_n,

A = ,

у пам'яті послідовно записуються матриці A ₁, A ₂, … A_n.

Для реалізації відповідної рекурсивної функції нам зручно було б мати матрицю B, у якої б матриці B ₁, B ₂, …, B_n були розміщені в послідовних блоках пам'яті. Цього можна досягти, послідовно записуючи в одновимірний масив елементи вихідної матриці з кроком n. Спочатку записуємо 1-й елемент, потім n -й, 2 n -й, 3 n -й,…, потім 2-й, 2 + n -й, 2 + 2 n -й,... Цю процедуру реалізуємо у функції: