3937. Цифровой корень

 

Цифровым корнем (digital root) числа n называется следующее число: берётся сумма цифр числа n, затем сумма цифр у получившегося числа и так далее, пока не получится однозначное число.

Ваша задача – отсортировать данный массив по возрастанию цифровых корней его элементов. Если цифровые корни двух чисел равны, то раньше должно идти меньшее число.

 

Вход. В одной строке заданы элементы массива. Длина массива не превосходит 200, каждое число положительно и не превышает 109.

 

Выход.  Вывести массив, отсортированный в порядке возрастания цифрового корня.

 

Пример входа 1

Пример выхода 1

15 14 13 12 11 10 9 8 7

10 11 12 13 14 15 7 8 9

 

 

Пример входа 2

Пример выхода 2

80 61 51 41 22 1

1 22 41 51 61 80

 

 

РЕШЕНИЕ

сортировка

 

Анализ алгоритма

Реализуем компаратор, сортирующий элементы массива по возрастанию их цифрового корня. Если цифровые корни чисел равны, то сортируем их по возрастанию.

 

Реализация алгоритма

Объявим массив для хранения чисел.

 

#define MAX 200

int m[MAX];

 

Сумма цифр числа n.

 

int sum(int n)

{

  return (n < 10) ? n : sum(n/10) + n % 10;

}

 

Цифровой корень числа n.

 

int digSum(int n)

{

  while (n > 9) n = sum(n);

  return n;

}

 

Компаратор – функция сравнения.

 

int f(int a, int b)

{

  if (digSum(a) == digSum(b)) return a < b;

  return digSum(a) < digSum(b);

}

 

Основная часть программы. Читаем массив чисел.

 

n = 0;

while(scanf("%d",&m[n]) == 1) n++;

 

Сортируем массив.

 

sort(m,m+n,f);

 

Вывод элементов массива.

 

for(i = 0; i < n; i++)

  printf("%d ",m[i]);

printf("\n");

 

Реализация алгоритма – MergeSort

 

#include <cstdio>

#include <algorithm>

#include <vector>

using namespace std;

 

int i, x;

vector<int> v;

 

int sum(int n)

{

  return (n < 10) ? n : sum(n / 10) + n % 10;

}

 

int digSum(int n)

{

  while (n > 9) n = sum(n);

  return n;

}

 

int f(int a, int b)

{

  if (digSum(a) == digSum(b)) return a < b;

  return digSum(a) < digSum(b);

}

 

void merge(vector<int>& a, int bleft, int bright, int cleft, int cright)

{

  // a[bleft..bright] and a[cleft..cright] are merged into a[bleft..cright]

  int i, left = bleft, len = cright - bleft + 1;

 

  int* res = new int[len];

  for (i = 0; i < len; i++)

  {

    if ((bleft > bright) || (cleft > cright)) break;

    if (f(a[bleft], a[cleft])) res[i] = a[bleft], bleft++;

    else res[i] = a[cleft], cleft++;

  }

 

  while (bleft <= bright) res[i++] = a[bleft++];

  while (cleft <= cright) res[i++] = a[cleft++];

 

  for (i = left; i < left + len; i++) a[i] = res[i - left];

  delete[] res;

}

 

void mergeSort(vector<int>& a, int left, int right)

{

  if (left >= right) return;

  int middle = (left + right) / 2;

  mergeSort(a, left, middle);

  mergeSort(a, middle + 1, right);

  merge(a, left, middle, middle + 1, right);

}

 

int main(void)

{

  while (scanf("%d", &x) == 1)

    v.push_back(x);

 

  mergeSort(v, 0, v.size() - 1);

 

  for (i = 0; i < v.size(); i++)

    printf("%d ", v[i]);

  printf("\n");

  return 0;

}

 

Реализация алгоритма – QuickSort

 

#include <cstdio>

#include <algorithm>

#include <vector>

using namespace std;

 

int i, x;

vector<int> v;

 

int sum(int n)

{

  return (n < 10) ? n : sum(n / 10) + n % 10;

}

 

int digSum(int n)

{

  while (n > 9) n = sum(n);

  return n;

}

 

int f(int a, int b)

{

  if (digSum(a) == digSum(b)) return a < b;

  return digSum(a) < digSum(b);

}

 

void swap(int &i, int &j)

{

  int temp = i; i = j; j = temp;

}

 

int Partition(vector<int>& m, int L, int R)

{

  int x = m[L];

  int i = L - 1, j = R + 1;

  while (1)

  {

    do j--; while (f(x, m[j]));

    do i++; while (f(m[i], x));

    if (i < j) swap(m[i], m[j]); else return j;

  }

}

 

void QuickSort(vector<int>& m, int L, int R)

{

  if (L < R)

  {

    int q = Partition(m, L, R);

    QuickSort(m, L, q); QuickSort(m, q + 1, R);

  }

}

 

int main(void)

{

  while (scanf("%d", &x) == 1)

    v.push_back(x);

 

  QuickSort(v, 0, v.size() - 1);

 

  for (i = 0; i < v.size(); i++)

    printf("%d ", v[i]);

  printf("\n");

  return 0;

}

 

Java реализация

 

import java.util.*;

 

public class Main

{

  public static int sum(int n)

  {

    return (n < 10) ? n : sum(n/10) + n % 10;

  }

 

  public static int digSum(int n)

  {

    while (n > 9) n = sum(n);

    return n;

  }

  public static class MyFun implements Comparator<Integer>

  {

    public int compare(Integer a, Integer b)

    {

      if (digSum(a) == digSum(b)) return a - b;

      return digSum(a) - digSum(b);

    }

  }

 

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    ArrayList<Integer> m = new ArrayList<Integer>();

    while(con.hasNext()) m.add(con.nextInt());

 

    Collections.sort(m, new MyFun());

   

    for(int i = 0; i < m.size(); i++) System.out.print(m.get(i) + " ");

    System.out.println();

    con.close();

  }

}