Вероятность того, что натуральное N-значное число является палиндромом и следующий палиндром

В первой задаче, наверное, можно рассуждать так:

• если разрешить лидирующие нули, имеем 10N N-значных чисел;
• палиндромами считаем числа, для которых первые N/2 цифр совпадают с последними N/2, прочитанными в обратном порядке;
• для чётного и нечётного количества цифр в числе нам придётся брать, соответственно, N/2 и (N-1)/2 цифр;
• вероятность быть палиндромом будет равна 10ceil(N/2) / 10N или 1 / 10floor(N/2).

А вот вторая задача - найти для заданного натурального числа следующий за ним наименьший палиндром, видимо, проще программируется, чем решается аналитически.

#include <iostream>
using namespace std;

void printArray (int arr[], int n) {
 int i;
 for (i = 0; i < n; i++) cout << arr[i] << " ";
 cout << endl;
}

int only9 (int* num, int n) {
 int i;
 for (i = 0; i < n; ++i) if (num[i] != 9) return 0;
 return 1;
}

void generateUtil (int num[], int n) {
 int mid = n / 2;
 bool leftsmaller = false;
 int i = mid - 1;
 int j = (n % 2) ? mid + 1 : mid;
 while (i >= 0 && num[i] == num[j]) { i--; j++; }
 if (i < 0 || num[i] < num[j]) leftsmaller = true;
 while (i >= 0) {
  num[j] = num[i]; j++; i--;
 }
 if (leftsmaller == true) {
  int carry = 1;
  i = mid - 1;
  if (n % 2 == 1) {
   num[mid] += carry;
   carry = num[mid] / 10;
   num[mid] %= 10;
   j = mid + 1;
  }
  else j = mid;
  while (i >= 0) {
   num[i] += carry;
   carry = num[i] / 10;
   num[i] %= 10;
   num[j++] = num[i--];
  }
 }
}

void generateNextPalindrome (int num[], int n) {
 int i;
 cout << "Next palindrome is ";
 if (only9(num, n)) { //Если только девятки
  cout << "1 ";
  for (i = 1; i < n; i++) cout << "0 ";
  cout << "1";
 }
 else {
  generateUtil(num, n);
  printArray(num, n);
 }
}

int main() {
 int num[] = { 9, 4, 1, 8, 7, 9 };
  //число для удобства сразу задаем масивом
 int n = sizeof(num) / sizeof(num[0]);
 generateNextPalindrome(num, n);

 cin.get();
 return 0;
}

15.09.2019, 15:49 [1547 просмотров]