Построить функцию intdigit (longx, intn) возвращающую n-ую цифру справа числа x
Вопросы на экзамен по информатике: 1. Есть массив строк. Нужно отсортировать их по первой букве (только по первой! на остальные не обращаем внимания) в алфавитном порядке. Какой из трёх алгоритмов ПРОСТОЙ сортировки нужно для этого выбрать? Решение: сначала выделим различия между сортировкой массива из N чисел и сортировкой массива из N строк. Количество сравнений не изменяется. А вот количество перестановок элементов очень сильно увеличивается, т.к. надо поменять местами не два числа, а две строки, то есть фактически два массива чисел. Поэтому нужно выбрать сортировку с минимальным количеством перестановок. Это сортировка методом выбора максимума (минимума)( сортировка выбором).
Перевести отрицательное целое число (он любое может назвать) в дополнительный код.
Взять модуль, перевести в обратный код(инвертирование) и прибавить 1 к младшему разряду.
Есть ли смысл применять метод барьера в поиске подстроки в строке?
Ответ: нет смысла, т.к. в этом случае барьером будет целый образец, который мы ищем, в конце строки поиска. Если образец длинный, нужно выделять много места в строке поиска, а операция проверки теперь состоит не просто из проверки на равенство, а из нескольких проверок на равенство. В общем, чем длиннее образец, который мы ищем, тем меньше смысл в использовании метода барьера. Нет смысла, т.к. от этого мы особо ничего не выиграем.
|
|
|
4. Дан двумерный массив int A[N][M]. Как с помощью указателя обратиться к элементу A[i][j]?
Ответ: *(A+i*M+j) – не ок.
Ответ: *(*(A+i)+j)
5. В функцию, которая ищет число в массиве, передаётся массив таким образом:
intfunc( int A[N], int b )
Можно ли здесь применить метод барьера?
Ответ: нет, т.к. в функцию передаётся массив фиксированного размера, а чтобы применить метод барьера, нужно добавить один элемент к массиву.
Для чего нужен инвариант цикла?
Ответ: для двух целей: для составления правильного цикла и для проверки правильности цикла. Особенно инвариант помогает, если в задаче есть множество всяких математических условий, в практический смысл которых вникать не хочется.
Некоторые говорят, что нужно очень хорошо знать все сортировки. Даже желательно сортировку Шелла и деревом. Всё это есть в Вирте. Есть вопрос на определение сложности какой-нибудь сортировки. То есть нужно уметь вычислять C и M. Всё было на лекциях. Нужно вообще хорошо понимать смысл сложности. Сложности сортировок.
Роль алгоритма оптимального поиска на примере задачи про коммивояжёра.
Сравнить эффективность алгоритмов: простой сортировки, усовершенствованной, бинарного и линейного поиска, алгоритмов поиска подстроки в строке.
|
|
|
10. Передача и представление в памяти двумерного массива.
11. Сложность, какой алгоритм сортировки более эффективен.
12. Почему индексы массива начинаются с 0, а не с 1?
Адрес первой ячейки – А, второй (А+1) и так далее.
В C, имя массива, по существу, указатель, ссылка на ячейку памяти, поэтому массив выражение [n] относится к ячейке памяти н-элементов от начальной элемента. Это означает, что индекс используется в качестве смещения. Первый элемент массива именно содержится в ячейке памяти, которая относится к массиву (0 элементов от), поэтому она должна быть обозначена как массив [0].
Переписывание кр:
1. Представить число суммой цифр, если сумма больше 10 -считать сумму заново.
int A(long x)
{
int res = 0;
longtmp = x;
while(1)
{
while(tmp> 0)
{
res += tmp % 10;
tmp /= 10;
}
if(res > 10)
{
tmp = res;
res = 0;
}
else
break;
}
return res;
}
Задачи на экзамене:
1. Размерность типа данных int( в битах )
minint=1;
while (minint<<1) minint = minint<<1;
maxint = minint - 1;
a = (maxint - minint) + 1;
b = 2;
do {
b *= 2;
sizeint++;
} while (b != a)
2. Реализация strcmp();
Int strcmp(char *s1, char *s2)
{
While (*s1 || *s2) //пока не дошли до конца
|
|
|
If (*s1-*s2) return (*s1-*s2);
Else
{ s1++; s2++}
Return 0;
}
Возвращает 0, если совпадает, число <0, если s1<s2, >0, если s2>s1.
3. Палиндром ( изк.р.)(еще два варианта в тетради). (Билет 11)
Int p(long x);
{ long n=x, m=0;
While (n>0)
{
M = m*10 + n%10;
N=n/10;
}
If (m==x) return 0;
Else return 1;}
4. Вывестивсе числа в случайном порядке(правая лучше)
Нельзя заменить заголовок второго цикла на n.
Rand()%3+1 от 1 до 3, Rand()% 3 – от 0 до 2
int A[2^(8*sizeof(int))]; // [N]
voidprintNumbers(int N) {
inti,j, A[N];
int x;
for (i = 0; i< N; i++) {
A[N] = i;
}
j = N;
for (i = 0; i< N; i++) {
x = rand() % j;
printf("%d\n", A[x]);
A[x] = A[j];
j--;
}
}
voidrand_print(int N)
{
inti,j,n=N-1;
for(i=o;i<N;i++) A[i]=i;
for(i=0;i<N-1;i++,n--)
{
j=rand();
j%=n;
printf("%d",A[j]);
A[j]=A[n];
}
printf("%d",A[0]);
}
5. Задача о Ханойских башнях
| void move( int k; // откуда int l; //куда int n; //сколько ) { if (n==1) printf (“Ход %dна %d”, k, l); Else { Int t; t = 6-k-l; ( или 6/k/l) move(k,t,n-1); move(k,l,1); move(t,l,n-1); }} |
6. Бинарный поиск элемента в массиве
intbinsearch(int x, int v[], int n)
{
int low, high, mid;
low = 0;
high = n - 1;
while (low <= high) {
mid = (low+high)/2;
if (x < v[mid])
high = mid + 1;
else if (x > v[mid])
low = mid + 1;
else /* found match */
return mid;
}
return -1; /* no match */
7. Сумма цифр в числе
Int f(int m){ int s=0;
While (m/10) {
S += m%10;
M= m/10; }
S=s+m;
Return s;
8. Число различных элементов в символьном массиве
|
|
|
| int main() { inti, count = 0; char a[] = { "hctrokahhf" }; int l = strlen(a); qsort(a, l, sizeof(char), strcmp); for (int i = 0; i< l; i++) printf("%c", *(a + i)); for (i = 1; i<= l; i++) { if (a[i] != a[i - 1]) count++; } printf("\n%d", count); system("pause"); }} |
{ inti, l;
int k=1;
l=strlen(s);
for(i=1;i<l;i++){
if(*s!=*(s+i)){
k++;
}
if(*s==*(s+i)){
k=0;
}
}
9. Сгенерировать все перестановки в целочисленном массиве (Билет 1).
void p (int n)
{ inti;
if(n==1){
printf (A);
} return n;
for(i=0;i<n;i++){
swap(&A[n-1], &A[n-1-i]);
p(n-1);
swap(&A[n-1], &A[n-1-i]);
Здесь функция printf выводит массив, а функция swap меняет два элемента массива.
intn;
intb[100]; // массив с числами 1,..., n
void rec(inti)
{ int j, t;
if(i==n)
{ for(i=0; i<n; ++i)
printf("%d%c",b[i],i<n-1?' ':'\n');
return;
}
// подстановка на i-ое место всех элементов с i по n-1
for(j=i; j<n; ++j)
{
t=b[i];
b[i]=b[j];
b[j]=t;
rec(i+1);
}
// восстановление состояния массива
t=b[i];
for(j=i+1; j<n; ++j)
b[j-1]=b[j];
b[n-1]=t;
}
10. Функция, возвращающая i и j такие, чтобы сумма эл-тов в i-ой строке равнялась сумме в j-ом столбце.
#include <stdio.h>
#define M 5
#define N 4
int MASS[M][N];
int main()
{
inti, j, SUMM_i = 0, SUMM_j = 0, buf = 1, K = 0, Z = 0;
intn;
for (i = 0; i<M; i++)//заполняем массив как нам хочется
for (j = 0; j < N ; j++)
MASS[i][j] = 2 * 2 + 2 * i - 9;
MASS[1][0] = 2; MASS[1][1] = 2; MASS[1][2] = 2; MASS[1][3] = 2;
MASS[0][3] = 2; MASS[1][3] = 2; MASS[2][3] = 2; MASS[3][3] = 2; MASS[4][3] = 0;
for (i = 0; i<M; i++) //пробегаем каждую строку массива
{
n = N - 1;
SUMM_i = 0;
for (j = 0; j < N; j++)
SUMM_i = SUMM_i + MASS[i][j];//суммаэлементовi-тойстроки
while (buf&&n>= 0)// пробегаем в цикле все столбцы массива
{
SUMM_j = 0;
for (j = 0; j < M; j++)
SUMM_j = SUMM_j + MASS[j][n];// суммаэлементов N-ногостолбца
if (SUMM_i == SUMM_j)// если суммы равны, то
{
K = i;//запоминаем индекс строки
Z = n;//запоминаем индекс столбца
buf = 0;
}
n--;
}
}
printf("%d\n%d\n", K, Z);
system("Pause");
}
11. Есть одномерный массив целых чисел и нужно построить функцию, получающую на вход вещественное число x и возвращающую индекс элемента, который ближе всего к этому числу.
int a[n];
int i;
for (int i = 0; i< n; i++)
{
a[i] = i + 7 - 1;
}
float x = 7.2;
int min = fabs(a[0]-x);
int fin;
for (i = 0; i< n; i++)
{
if ((fabs(a[i] - x)) < min)
{
min = fabs(a[i]-x);
fin = i;
}
}
printf("%d", fin);
system("pause");
12. Функцияstrcpy (char *s1, char *s2) ,билет 12.
13. Даны A[n], B[n], x. Написать функцию, которая возвращала бы такие i и j, что A[i]+B[j] было максимально приближенно к x.
#include<math.h> // для функции fabs, возвращающей модуль числа
voidfunc(int N ,float A[N], float B[N], int *i, int *j, float x)
{
intii,jj;
floata,min;
int*i=0;
int *j=0;
min=fabs(A[0]+B[0]-x);
for (ii=0; ii<N; ii++)
for (jj=0; jj<N; jj++)
if ((a=fabs(A[ii]+B[jj]-x))<min)
{
*i=ii;
*j=jj;
min=a;
}
}
14. Реализация strcat(); Билет 7.
char *strcat(char *s1, char *s2)
{
Int i=0; char *t = s1;
While (*s1++) s1--;
While (*s1++ = *s2++);
Return t;
}
15. Билет 5. Функция, выдаёт частное и остаток от деления xна y, нельзя пользоваться / и % .
Void f(int x, int y, int *m, int *k)
{
intq, x, p, y;
q = x; p = 0;
while (q>= y)
{
q = q - y;
p++;
}
*m = p; // частное
*k = q; // остаток
}
p*y + q = const = x
16. Метод генерации случайной перестановки ( Тасование Фишера-Йетса).(не ок)
voidswap(int *c, inty, intt)
{
inttmp = c[y];
c[y] = c[t];
c[t] = c[y];
}
intmain()
{
inti, j;
inta[5] = {1, 2, 3, 4, 5 };
for (i = 0; i< 5; i++)
printf("%d", a[i]);
system("pause");
for (i = 0; i< 5; i++)
{
j = rand() % 5;
swap(a, j, i);
}
}
for (i = 0; i< 5; i++)
printf("%d", a[i]);
system("pause");
Cам алгоритм:Для тасования массива a из n элементов (индексы 0..n-1):
для всехiотn − 1 до 1 выполнить
j ← случайное число 0 ≤ j ≤ i
обменять местами a[j] и a[i]
functionrandomPermutation(a:array[1..n] of integer):array[1..n] of integer // n — длинамассива
for i = 1 to n
j = 
return a
17. Билет про ЛКГ ,параметры
Построить функцию intdigit (longx, intn) возвращающую n-ую цифру справа числа x.
int digit(long x, int n)
{
int l, a;
charbuf[100];
char k[1];
ltoa(x,buf,10);
l=strlen(buf);
k[0]=buf[l-n];
a=atoi(k);
return(a);
}
2. Реализоватьфункцию int strncmp(char*s1,char*s2,n)
intstrncmp(char*s1, char*s2, n)
{ inti=0;
while (*s1++=*s2++ &&i<=n && *s1!=NULL && *s2!=NULL) i++
if (*s1==*s2) return(0);
if (*s1>*s2) return (1);
if (*s1<*s2) return(-1);
3. Реализоватьфункцию char*strncat(char*s1,char*s2,n)
char*strncat(char*s1, char*s2,n)
{char *sav=s1;
inti=0;
while (*s1) s1++;
while (*s2 &&i<=n)
{i++;*s1=*s2;s1++;s2++;}
return(sav);
1. Реализовать функции int strlen(char *s).
intstrlen(char *s)
{
intlen=0;
while(*s++) len++;
return( len);
}
2. Реализоватьфункцию char*strcpy(char *s1,char*s2)
char*strcpy(char*s1, char*s2)
{
char *sav =s1;
while(*s1++=*s2++);
return(sav);
}
3. Реализоватьфункцию char*strcat(char*s1,char s2)
char*strcat(char*s1, char*s2)
{
char *sav =s1;
while(*s1){
s1++;
}
while(*s2){
*s1=*s2;
s1++;
s2++;
}
return(sav);
}
4. Реализоватьфункцию char*strchr(char*s,char c)
char *strchr(char*s, char c)
{
while (((*s)!=c) && *s!=’\0’) s++;
if (*s==0) return(0);
return(s);
}
5. Реализоватьфункцию char*strncpy(char*s1,char*s2,n)
char*strncpy(char*s1,char*s2, n)
{char *sav=s1;
inti=0;
while (*s2 &&i<=n) {*s1=*s2;s1++;s2++;}
return(sav);
Задачи из лекций:
1. Программа, определяющая размер типов без использования sizeof.
int main()
{
int digit1, digit2;
charmaxchar, minchar = 0;
unsigned char maxuchar = -1, minuchar = 1;
intmaxint, minint = 1, sizeint = 1, sizeuint = 1, sizeuchar = 1, sizechar = 1, sizeshort = 1, sizelong = 1;
unsigned int maxuint = -1, minuint = 0;
shortmaxshort, minshort = 0;
longmaxlong, minlong = 1;
int a, b;
while (minchar>= 0) minchar++;
maxchar = minchar - 1;
digit1 = (maxchar - minchar) + 1;
while (digit1 % 2 == 0)
{
digit1 = digit1 / 2;
sizechar++;
}
while (minuchar> 0) minuchar++;
maxuchar = minuchar - 1;
digit1 = (maxuchar - minuchar) + 1;
while (digit1 % 2 == 0)
{
digit1 = digit1 / 2;
sizeuchar++;
}
while (minint*2) minint = minint*2;
maxint = minint - 1;
digit1 = (maxint - minint) + 1;
digit2 = 2;
do {
digit2 *= 2;
sizeint++;
} while (digit2 != digit1);
while (minuint *2) minuint = minuint *2;
digit1 = (maxuint - minuint) + 1;
digit2 = 2;
do {
digit2 *= 2;
sizeuint++;
} while (digit2 != digit1);
while (minshort>= 0) minshort ++;
maxshort = minshort - 1;
digit1 = (maxshort - minshort) + 1;
while (digit1 % 2 == 0)
{
digit1 = digit1 / 2;
sizeshort++;
}
while (minlong *2) minlong = minlong*2;
maxlong = minlong -1 ;
digit1 = (maxlong - minlong) + 1;
digit2 = 2;
do
{
digit2 = digit2 * 2;
sizelong++;
} while (digit2 != digit1);
}
2. Поиск минимума и максимума в массиве.
int a[5] = { 5, 4, 3, 7, 8};
inti = 0;
int max = a[0];
int min = a[0];
for (i = 0; i< 5; i++)
{
if (a[i]> max) max = a[i];
if (a[i] < min) min = a[i]; }
3. Дан упорядоченный массив, найти число различных чисел.
int a[7] = {1,3,3,3,5,9,9};
int i;
int count = 0;
for (i = 0; i< 7; i++)
{
if (a[i + 1] != a[i]) count++;
}
4. Найти сумму подмассива длиной m
Int arr[N]; int m, sum = 0;
If (m<=N){
For (int j=0; j<=(N-m); j++)
{
For (int i=j; i<m+j; i++) { sum = sum+arr[i];} printf(“Sum #%d %d”, (j+1), sum);
Sum = 0;
}
}
Else printf(“Error: m>N”); }
5. Проверка на простоту целого х
int simple(int n)
{
if (n == 1) return 1;
for (int i = 2; i<= n / 2; i++)
if (!(n%i)) return 0;
return 1;
}
int main()
{
int n;
printf(" N=");
scanf("%d", &n);
if (n == 2) return -1;
if (simple(n)) return 0;
else return -1; }
6. N-ю цифру числа справа
int digit(long x, int n)
{
int t;
for (int i = 1; i<= n; i++){
t = x % 10;
x = x / 10;
}
printf("%d", t);
}
Дата добавления: 2018-02-28; просмотров: 466; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!