Bon un quick and dirty en C.
j’implémente directement une solution en base B quelconque (2≤B≤36). Dans la suite du texte je note Δ le plus grand chiffre de cette base (9 en base 10, F en base 16, 1 en base 2, …). L’idée de base commence par éliminer deux cas particuliers :
- les nombres composés uniquement de chiffres Δ (comme 11111 en base 2, 9 en base 10 ou encore BBBBBB en base 12). Cela me permet d’éviter le cas où le palindrome suivant contient plus de chiffres que le nombre de départ. Pour un palindrome du type Δⁿ, nextpal(Δⁿ)=1Δⁿ⁻¹1 ;
- puis les nombres composés d’un seul chiffre strictement plus petits que Δ, dans ce cas nextpal(n)=n+1 ;
Après ce filtre, on se retrouve donc avec un nombre d’au moins deux chiffres dont le palindrome suivant possédera le même nombre de chiffres.
Mon algo traverse ensuite plusieurs étapes :
- on part du milieu du nombre pour déterminer le plus grand palindrome interne, comme par exemple 22 dans 1223 ou 54345 dans 895434512 ;
- on copie la partie à gauche (si elle existe) du palindrome interne à sa droite ;
- si le nombre entier était un palindrome ou si le chiffre à gauche du palindrome interne était plus petit que celui à sa droite alors j’ajoute 1 à partir du milieu du nombre en propageant la retenue et en copiant en miroir à droite.
Par exemple : 808 → plus grand palindrome interne 808 → ajout de 1 à partir du milieu → 818 898 → plus grand palindrome interne 898 → ajout de 1 à partir du milieu → 908 → copie miroir → 909 3221 → plus grand palindrome interne 3221 → copie miroir hors palindrome interne → 3223 12328 → plus grand palindrome interne 12328, chiffre à gauche plus petit que celui à droite → copie miroir → 12321 → ajout de 1 à partir du milieu 12421 → copie miroir → 12421 3284 → plus grand palindrome interne 3284 → chiffre à plus petit que celui à doite → copie miroir → 3223 → ajout de 1 à partir du milieu → 3323 → copie miroir → 3333
code vite fait :
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static char digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
static uint8_t values[] = {
['0'] = 0, ['1'] = 1, ['2'] = 2, ['3'] = 3, ['4'] = 4, ['5'] = 5,
['6'] = 6, ['7'] = 7, ['8'] = 8, ['9'] = 9, ['a'] = 10, ['b'] = 11,
['c'] = 12, ['d'] = 13, ['e'] = 14, ['f'] = 15, ['g'] = 16, ['h'] = 17,
['i'] = 18, ['j'] = 19, ['k'] = 20, ['l'] = 21, ['m'] = 22, ['n'] = 23,
['o'] = 24, ['p'] = 25, ['q'] = 26, ['r'] = 27, ['s'] = 28, ['t'] = 29,
['u'] = 30, ['v'] = 31, ['w'] = 32, ['x'] = 33, ['y'] = 34, ['z'] = 35,
['A'] = 10, ['B'] = 11, ['C'] = 12, ['D'] = 13, ['E'] = 14, ['F'] = 15,
['G'] = 16, ['H'] = 17, ['I'] = 18, ['J'] = 19, ['K'] = 20, ['L'] = 21,
['M'] = 22, ['N'] = 23, ['O'] = 24, ['P'] = 25, ['Q'] = 26, ['R'] = 27,
['S'] = 28, ['T'] = 29, ['U'] = 30, ['V'] = 31, ['W'] = 32, ['X'] = 33,
['Y'] = 34, ['Z'] = 35,
};
static bool valid[] = {
['0'] = true, ['1'] = true, ['2'] = true, ['3'] = true, ['4'] = true,
['5'] = true, ['6'] = true, ['7'] = true, ['8'] = true, ['9'] = true,
['a'] = true, ['b'] = true, ['c'] = true, ['d'] = true, ['e'] = true,
['f'] = true, ['g'] = true, ['h'] = true, ['i'] = true, ['j'] = true,
['k'] = true, ['l'] = true, ['m'] = true, ['n'] = true, ['o'] = true,
['p'] = true, ['q'] = true, ['r'] = true, ['s'] = true, ['t'] = true,
['u'] = true, ['v'] = true, ['w'] = true, ['x'] = true, ['y'] = true,
['z'] = true, ['A'] = true, ['B'] = true, ['C'] = true, ['D'] = true,
['E'] = true, ['F'] = true, ['G'] = true, ['H'] = true, ['I'] = true,
['J'] = true, ['K'] = true, ['L'] = true, ['M'] = true, ['N'] = true,
['O'] = true, ['P'] = true, ['Q'] = true, ['R'] = true, ['S'] = true,
['T'] = true, ['U'] = true, ['V'] = true, ['W'] = true, ['X'] = true,
['Y'] = true, ['Z'] = true,
};
typedef struct {
char *input;
int base;
bool done;
size_t number_len;
uint8_t *number;
size_t nextpal_len;
uint8_t *nextpal;
} input_data_t;
input_data_t get_data(const char *input, int base);
void compute_nexpal(input_data_t *data);
void display(input_data_t data);
int main(int argc, char *argv[]) {
input_data_t data = get_data(argv[1], argv[2] ? atoi(argv[2]) : 10);
compute_nexpal(&data);
display(data);
}
input_data_t get_data(const char *input, int base) {
if (base < 2 || base > 36) {
fprintf(stderr, "base invalide\n");
exit(EXIT_FAILURE);
}
input_data_t data;
data.input = strdup(input);
data.base = base;
data.number_len = strlen(input);
if (data.number_len < 1) {
fprintf(stderr, "nombre invalide\n");
exit(EXIT_FAILURE);
}
data.number = malloc(data.number_len * sizeof *data.number);
bool all_last_digit = true;
for (size_t i = 0; i < data.number_len; i++) {
if (!valid[(int)input[i]]) {
fprintf(stderr, "caractère invalide\n");
exit(EXIT_FAILURE);
}
uint8_t value = values[(int)input[i]];
if (value != base - 1)
all_last_digit = false;
if (value >= base) {
fprintf(stderr, "chiffre invalide\n");
exit(EXIT_FAILURE);
}
data.number[i] = value;
}
if (all_last_digit) {
data.done = true;
data.nextpal_len = data.number_len + 1;
data.nextpal = calloc(data.nextpal_len, sizeof *data.nextpal);
data.nextpal[0] = data.nextpal[data.nextpal_len - 1] = 1;
} else if (data.number_len == 1) {
data.done = true;
data.nextpal_len = data.number_len;
data.nextpal = calloc(data.nextpal_len, sizeof *data.nextpal);
data.nextpal[0] = values[(int)input[0]] + 1;
} else {
data.done = false;
data.nextpal_len = data.number_len;
data.nextpal = calloc(data.nextpal_len, sizeof *data.nextpal);
memcpy(data.nextpal, data.number, data.number_len);
}
return data;
}
void compute_nexpal(input_data_t *data) {
if (data->done)
return;
ssize_t middle = data->nextpal_len / 2;
ssize_t left = middle - 1;
ssize_t right = middle + (data->nextpal_len % 2);
bool left_smaller = false;
while (left >= 0 && data->nextpal[left] == data->nextpal[right]) {
left--;
right++;
}
left_smaller = (left < 0 || data->nextpal[left] < data->nextpal[right]);
while (left >= 0) {
data->nextpal[right] = data->nextpal[left];
right++;
left--;
}
if (left_smaller) {
int carry = 1;
left = middle - 1;
if (data->nextpal_len % 2) {
data->nextpal[middle] += carry;
carry = data->nextpal[middle] / data->base;
data->nextpal[middle] %= data->base;
right = middle + 1;
} else {
right = middle;
}
while (left >= 0) {
data->nextpal[left] += carry;
carry = data->nextpal[left] / data->base;
data->nextpal[left] %= data->base;
data->nextpal[right++] = data->nextpal[left--];
}
}
data->done = true;
}
void display(input_data_t data) {
printf("le palindrome suivant %s en base %d est : ", data.input, data.base);
for (size_t i = 0; i < data.nextpal_len; i++)
putchar(digits[data.nextpal[i]]);
putchar('\n');
}
Le code mériterait largement une simplification. J’ai pris le parti de ne saisir que des chaînes que je transforme en tableau d’entiers pour les manipulations.
Du coup en base 36, nextpal(256344510514743751332437247280545791⏨,36)=256344510514743751399753977111200702⏨
voilà voilà
+2
-0
Edit: mise en forme de l’énoncé …
