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);
сработает только для положительных значений.
29.12.2015, 10:12 [15023 просмотра]