БлогNot. 15 не пригодившихся задачек за декабрь-2015

Помощь дата->рейтинг Поиск Почта RSS канал Статистика nickolay.info Домой

15 не пригодившихся задачек за декабрь-2015

Что накопилось и может ещё пригодиться. Везде C/C++, все коды проверялись в Visual Studio 2010 или 2015. Для быстрого поиска нужного слова на странице используйте в браузере комбинацию клавиш Ctrl+F.

1. Составить программу для "графического" изображения делимости чисел от 1 до n. В каждой строке консоли напечатать очередное число и перечислить все делители этого числа.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h> 
 
int main() {
 int n=100,i,j;
 for (i=1; i<=n; i++) {
  printf ("\n%d: ",i);
  for (j=1; j<=i; j++) if (i%j==0) printf ("%d ",j);
 }
 fflush(stdin); getchar(); return 0;
}

2. Дан одномерный массив. Определить минимальное счастливое число среди чисел с четным количеством цифр. Счастливое число - это число, у которого сумма цифр первой половины числа равна сумме второй половины.

Пример того, как "красиво" найти количество цифр в целом числе (count_digits).

#include <stdio.h>
#include <limits.h>
 
int count_digits (long int num){ return ( num /= 10 ) ? 1 + count_digits(num) : 1; }
 
int happy_digit (long int num) {
 //работает и для нечетного количества цифр
 int sum1=0,sum2=0,i=0,n=count_digits(num);
 if (n<2) return 0;
 while (num!=0) {
  if (i<n/2) sum1 += num%10;
  else if (!(n%2==1 && i==n/2)) sum2 += num%10;
  num/=10;
  i++;
 }
 return sum1==sum2;
}
 
int main (){
 const int n = 7;
 long int a[n] = { 4224, 1324, 132, 434, 123321, 4004, 12 };
 long int min=LONG_MAX,c;
 int i;
 for (i=0; i<n; i++) {
  c=count_digits(a[i]);
  if (c%2==0 && happy_digit(a[i]) && a[i]<min) min=a[i];
 }
 printf ("\n%ld",min);
 fflush (stdin);
 getchar ();
 return 0;
}

3. Дан символ C и строки S, S0. Перед каждым вхождением символа C в строку S вставить строку S0 (используются си-строки, а не класс string).

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
//if s[i]==c, insert s0 before it. no memory control!
char *strins (char *s, char *s0, char c) {
 int slen=strlen(s);
 int s0len=strlen(s0);
 int i,j;
 for (i=0; i<slen; i++) {
  if (s[i]==c) {
   for (j=slen; j>=i; j--) s[j+s0len]=s[j];
   for (j=0; j<s0len; j++) s[i+j]=s0[j];
   slen+=s0len; i+=s0len;
  }
 }
 return s;
}
 
int main (){
 char c='l';
 const int SIZE=256;
 char *s = (char *)malloc(SIZE*sizeof(char));
 strcpy(s,"lol, Hello, i'm test string! la-la-l");
 char *s0 = "123";
 char *ptr = strins(s,s0,c);
 puts(ptr);
 fflush (stdin);
 getchar ();
 return 0;
}

Функция strins, согласно условиям задачи, не контролирует использование оперативной памяти.

4. Занести в одномерный массив значения функции f(x,y) = (x + y)2, 0<=x<=5, 0<=y<=3, и вывести его на экран.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
double f(double x, double y) { return pow(x+y,2); }
 
int main (){
 double x1=0,x2=5,y1=0,y2=3,dx=1,dy=1; //границы по x,y и шаги
 int n=ceil((x2-x1+1)/dx)*ceil((y2-y1+1)/dy); //размерность массива, необязательно точная
 double *fa=(double *)malloc(n*sizeof(double));
 double x,y;
 int i=0;
 for (x=x1; x<=x2+1e-9; x+=dx) 
 for (y=y1; y<=y2+1e-9; y+=dy) fa[i++]=f(x,y);
 int j;
 for (j=0; j<i; j++) printf ("%.2lf ",fa[j]);
 fflush (stdin);
 getchar ();
 return 0;
}

5. Написать функцию вычисления F(N) = F(N-2)+3.5, с использованием рекурсии, при условии F(1)=1, F(0)=0.

#include <stdio.h>
 
double f(int n) { 
 if (n<1) return 0;
 else if (n<2) return 1;
 else return f(n-2)+3.5; 
}
 
int main (){
 for (int i=0; i<10; i++) printf ("f(%d)=%.2lf ",i,f(i));
 fflush (stdin);
 getchar ();
 return 0;
}

6. Транспонировать прямоугольную матрицу a[n][m] с выделением памяти для новой матрицы.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
 
int **transp (int n, int m, int **a) { //a[n][m] => at[m][n]
 int **at=(int**)malloc(m*sizeof(int *));
 int i,j;
 if (at==NULL) return NULL;
 for (i=0; i<m; i++) {
  at[i]=(int*)malloc(n*sizeof(int));
  if (at[i]==NULL) return NULL;
  
 }
 for (i=0; i<n; i++) for (j=0; j<m; j++) at[j][i]=a[i][j];
 return at;
}
 
void print_matrix(int n,int m,int **a) {
 int i,j;
 for (i=0; i<n; i++) {
  printf ("\n");
  for (j=0; j<m; j++) printf ("%d ",a[i][j]);
 }
}
 
int main () {
 const int n=3,m=2;
 int **a,i,j;
 a=(int**)malloc(n*sizeof(int *));
 for (i=0; i<n; i++) a[i]=(int*)malloc(m*sizeof(int));
 a[0][0]=1; a[0][1]=2;
 a[1][0]=3; a[1][1]=4;
 a[2][0]=5; a[2][1]=6;
 print_matrix(n,m,a);
 int **at=transp(n,m,a);
 print_matrix(m,n,at);
 fflush(stdin); getchar(); return 0;
}

7. Для заданного натурального n, например n=4, сформировать матрицу вида

1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3 

#include <iostream> 
using namespace std;
 
int main() {
 const int n=10;
 int a[n]={1,2,3,4,5,6,7,8,9,10};
 int a1[n][n],i,j;
 
 for (int i=0; i<n; i++) {
  int start = i;
  for (j=0; j<n; j++) {
   a1[i][j] = a[start++];
   if (start>n-1) start=0;
  }
 }
 
 for (i = 0; i < n; i++) {
  for (j = 0; j < n; j++) cout << a1[i][j] << ' ';
  cout << endl;
 }       
 
 cin.sync(); cin.get(); return 0;
}

8. Среди заданных натуральных чисел найти такие, десятичная запись которых не содержит одинаковых цифр.

#include <iostream> 
using namespace std;
 
int different_digits (int n) {
 int d[10],i;
 for (i=0; i<10; i++) d[i]=0;
 while (n) {
  if (d[n%10]++) break;
  n/=10;
 }
 return (n?0:1);
}
 
int main() {
 cout << 1234 << ": " << different_digits (1234) << endl;
 cout << 3213 << ": " << different_digits (3213) << endl;
 cout << 100 << ": " << different_digits (100) << endl;
 cout << 98170 << ": " << different_digits (98170) << endl;
 cin.sync(); cin.get(); return 0;
}

Здесь симпатична функция different_digits, возвращающая 1, если все цифры числа разные. Обратите внимание, что break срабатывает именно при d[n%10] (количество вхождений очередной цифры), большем 1, а не 0.

9. Используя рекурсивную функцию, найти сумму первых n элементов последовательности x[n] = 3 * x[n-1]+1, x[0] = 1.

#include <iostream> 
using namespace std;
 
int x(int n) { return (n==0 ? 0 : 3*x(n-1)+1); }
 
int main() {
 int sum=0;
 const int n=10; //сколько элементов суммировать
 for (int i=0; i<n; i++) {
  cout << x(i) << endl;
  sum+=x(i);
 }
 cout << "sum=" << sum << endl;
 cin.sync(); cin.get(); return 0;
}

10. Сравнить попарно все строки в матрице и вывести номера отличающихся пар строк.

#include <iostream> 
using namespace std;
 
int main() {
const int n=3,m=2;
 int a[n][m]={
 {1,2},
 {2,3},
 {1,2}
 };
 for (int i=0; i<n-1; i++)
 for (int j=i+1; j<n; j++) {
  int r=0;
  for (int k=0; k<m; k++) if (a[i][k]!=a[j][k]) { r=1; break; }
  cout << "strings " << i << " and " << j << " are " <<
   (r ? "not" : "") << " equal" << endl;
 }
 cin.sync(); cin.get(); return 0;
}

11. Найти порядковый номер наибольшего по значению элемента массива, являющегося симметричным в десятичном представлении.

#define _CRT_SECURE_NO_WARNINGS /*for Visual C++ 2015*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h> //В Borland C было values.h
 
int count_digits(int num) { //цифр в числе
    return (num /= 10) ? 1 + count_digits(num) : 1; 
}
 
int symmetric_number(int n) { //1, если число симметрично
    int count = count_digits(n),i;
    char *digits = (char *)malloc(count*sizeof(char));
    if (!digits) return 0;
    for (i = 0; i < count; i++) {
        digits[count-i-1] = abs(n % 10); //если число отрицательно - смотрим без знака
        n /= 10;
    }
    if (count == 1) return 1; //числа 0-9 считаем симметричными
    for (i = 0; i < count/2; i++) {
        if (digits[i] != digits[count-i-1]) return 0;
    }
    free (digits);
    return 1;
}
 
int main() {
    const int n = 8;
    int a[n] = { 1, 55, 31200, 676, 4884, 30503, 31412, 29692 };
    int i, nmax, max = -INT_MAX; //В Borland C было MAXINT
    for (i = 0; i < n; i++) {
        if (symmetric_number(a[i]) && a[i]>max) {
            max = a[i]; nmax = i + 1;
        }
    }
    printf("\nvalue=%d (number=%d)",max,nmax);
    fflush(stdin); getchar(); return 0;
}

P.S. Формально INT_MIN != -INT_MAX:

#define INT_MIN     (-2147483647 - 1) /* minimum (signed) int value */
#define INT_MAX       2147483647    /* maximum (signed) int value */

INT_MIN на 1 больше по модулю (7FFFFFFF или -2147483648 для 32 бит).

Так что код не сработает, только если массив заполнен одними значениями INT_MIN :) Возможно, и INT_MIN+1, т.к., сравнение ">", а не ">=".

Но эти числа всё равно несимметричные :)

Да и в Борланде "MININT", вроде бы, не было.

12. Задан массив m типа int и его размерность n. Найти значение максимального элемента массива без использования каких-либо операторов цикла.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <math.h>
using namespace std;
 
int maxi(int n, int *m)     {
 if (n > 0) return max(m[n], maxi(--n,m));
 else if(n == 0) return m[0];
}
 
int main() {
 const int n=10;
 int m[n] = {3,2,1,3,9,4,6,7,8,4};
 cout << maxi(n,m);
 
 cin.sync(); cin.get(); return 0;
}

Можно, конечно, пошутить и сделать с goto:

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
 
int main() {
 const int n=10;
 int m[n] = {5,2,1,3,9,4,6,7,8,2};
 int i = 0, max = m[0];
 l1:
 if(max < m[i]) max = m[i];
 i++;
 if(i >= n) goto l2;
 goto l1;
 l2:
 
 cout << max << endl;
 cin.sync(); cin.get(); return 0;
}

13. Переставить 3-й и 4-й биты младшего байта целого числа с помошью программного кода.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <bitset>
using namespace std;
 
int main() {
 int n=42;
 
 cout << n << " (" << bitset<32>(n) << ")" << endl;
 //нумерация бит в байте: 7654 3210
 int b3 = n&8, b4 = n&16; 
 n &= ~(1<<3); 
 if (b4) n|=(1<<3);
 n &= ~(1<<4); 
 if (b3) n|=(1<<4);
 cout << n << " (" << bitset<32>(n) << ")" << endl;
  
 cin.sync(); cin.get(); return 0;
}

Действия между операторами cout можно выполнить и в 4 оператора вместо 6 (первый код тоже поддаётся сокращению):

int b3 = ((n>>3) & 1);
int b4 = ((n>>4) & 1);
n = (n & (~0x18));
n |= ((b3<<4) | (b4<<3));

14. Определить наименьшее число сравнений, нужное для сортировки 4 значений по возрастанию.

Это число равно пяти, а не шести, как может показаться, если привыкнуть сравнивать каждый элемент с каждым (трудоёмкость этого действия соответствует количеству элементов выше или ниже главной диагонали квадратной матрицы размерностью n*n и равна (n2 - n)/2 = 6 при n=4).

Например, можно за 3 сравнения упорядочить 3 первых числа, потом среднее из чисел сравнить с оставшимся, и, в зависимости от результатов этого сравнения, выполнить ещё одно.

В доказательство возьмём все возможные комбинации чисел 1,2,3,4 и проверим на них функцию sort4, содержащую ровно 5 условных операторов.

Заодно main показывает, как реализовать стандартными средствами все перестановки элементов массива (вначале различные между собой элементы массива a должны быть упорядочены по возрастанию, чтоб сработал стандартный алгоритм).

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
using namespace std;

void swap (int &a, int &b) { int c=a; a=b; b=c; }

void sort4 (int &a, int &b, int &c, int &d) {
 if (a>b) swap(a,b);
 if (a>c) swap(a,c);
 if (b>c) swap(b,c); //за 3 сравнения сортируются 3 числа 
 if (b>d) { //сравнить среднее с 4-м
  swap(b,d);
  if (a>b) swap (a,b);
  swap(c,d);
 } 
 else if (c>d) swap(c,d);
}

int main () {
 int a[] = { 1, 2, 3, 4 };
 int len = sizeof(a) / sizeof(int);
 int *b = new int [len];
 do {
  cout << "From:";
  for (int i = 0; i < len; i++) {
   cout << a[i] << ",";
   b[i] = a[i]; //копия массива, так как в sort4 передаем по ссылке
  }
  sort4 (b[0],b[1],b[2],b[3]);
  cout << " to: ";
  for (int i = 0; i < len; i++) cout << b[i] << ",";
  cout << endl;
 } while (next_permutation (a, a + len));
 delete[] b;
 
 cin.sync(); cin.get(); return 0;
}

15. Поменять местами содержимое старшего и младшего байтов двухбайтового целого значения.

Работаем с типом short int, чтобы обеспечить 2 байта. Обратите внимание, как вывести число в двоичном виде стандартными средствами C++.

#include <iostream> 
#include <bitset>
using namespace std;

short int swapbytes(short int a) {
 return ((a & 0x00FF) << 8) | ((a & 0xFF00) >> 8);
}

int main() {
 short int a = -32767;
 cout << a << " (" << bitset<16>(a) << ")" << endl;
 a = swapbytes(a);
 cout << a << " (" << bitset<16>(a) << ")" << endl;
 cin.sync(); cin.get(); return 0;
}

Естественное, казалось бы,

 return (a<<8) + (a>>8);

сработает только для положительных значений.


теги: c++ алгоритм список учебное

29.12.2015, 10:12; рейтинг: 6510

  свежие записипоиск по блогукомментариистатистика

Наверх Яндекс.Метрика
© PerS
вход