Найти наибольшую комбинацию числ

@zlaskus · Регистрация: 26.02.2018

Студворк — интернет-сервис помощи студентам

На вход дается массив случайных чисел случайной длины, вводимый пользователем. Необходимо из этих чисел составить наибольшую комбинацию и ввести пользователю. Например если вбиты числа 9, 93, 986, 50 на выходе будет 9.986.93.50. Пожалуйста, помогите решить эту задачу.

@kalabuni · 15.05.2018, 14:51

расшифруйте понятие "наибольшая"
почему наибольшей вы указали 9.986.93.50., а не 986.93.50.9. и не 93.986.50.9.?

и что именно, и куда надо ввести пользователю?

@zlaskus · 15.05.2018, 15:13 **[ТС]**

Извините, опечатался. Число, которое образуется последовательностью 9.986.93.50 (число 99869350), больше других чисел, образованных другими комбинациями. Вывести пользователю нужно наибольшее получившееся число.

На вход пользователь дает числа которые сам пожелает. Ограничений по количеству чисел или размеру нет.

@kalabuni · 15.05.2018, 16:13

Сообщение от zlaskus

Ограничений по количеству чисел или размеру нет

таки и нет?
1. про максимальное числовое значение, представимое в JavaScript Number.MAX_VALUE ничего не слышали?
почитайте на досуге
спич не только о тех числах, что введёт пользователь, а и о тех, что могут получиться конкатенацией из введённых

2. надеюсь, понимаете, что задача решается комбинаторным методом перестановки введённых пользователем чисел, а число перестановок вычисляется как факториал количества этих чисел.
уверяю: браузер подвиснет даже при десяти введённых пользователем числах
для справки: 10! = 3 628 800

@Jewbacabra · 16.05.2018, 13:29

Кликните здесь для просмотра всего текста

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
let numbers = [9, 93, 986, 50]
numbers = numbers.map(n => n.toString()).sort().reverse()
 
let tree = {
    value: null,
    fullValue: null,
    token: false,
    leaves: []
};
 
function putNumberIntoTree(tree, number, prefix = '') {
    let size = number.length
    let ch = number.charAt(0)
    let found = false
 
    for (var leave of tree.leaves) {
        if (leave.value === ch) {
            found = true
            leave.token = size === 1
            break
        }
    }
 
    if (found === false) {
        leave = {
            value: ch,
            fullValue: prefix + ch,
            token: size === 1,
            leaves: []
        }
        tree.leaves.push(leave)
    }
 
    if (size === 1) {
        return
    }
 
    putNumberIntoTree(leave, number.substr(1), prefix + ch)
}
 
for (let num of numbers) {
    putNumberIntoTree(tree, num)
}
 
let result = []
function findMaxConcat(tree) {
    let tmp = ''
    if (tree.token === true) {
        tmp = tree.fullValue
    }
 
    let processed = false
    for (let leave of tree.leaves) {
        if (tmp !== '' && processed === false && leave.value <= tree.value) {
            result.push(tmp)
            processed = true
        }
        findMaxConcat(leave)
    }
 
    if (tmp !== '' && processed === false) {
        result.push(tmp)
    }
}
 
findMaxConcat(tree)
console.log(result.join('.'))

Добавлено через 7 часов 22 минуты

Исправленный вариант

Кликните здесь для просмотра всего текста

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
let numbers = [9, 93, 986, 50, 9869, 98699, 98698, 99]
numbers = numbers.map(n => n.toString()).sort().reverse()
 
let tree = {
    value: null,
    fullValue: null,
    token: false,
    leaves: []
};
 
function putNumberIntoTree(tree, number, prefix = '') {
    let size = number.length
    let ch = number.charAt(0)
    let found = false
 
    for (var leaf of tree.leaves) {
        if (leaf.value === ch) {
            found = true
            leaf.token = leaf.token || size === 1
            break
        }
    }
 
    if (found === false) {
        leaf = {
            value: ch,
            fullValue: prefix + ch,
            token: size === 1,
            leaves: []
        }
        tree.leaves.push(leaf)
    }
 
    if (size === 1) {
        return
    }
 
    putNumberIntoTree(leaf, number.substr(1), prefix + ch)
}
 
for (let num of numbers) {
    putNumberIntoTree(tree, num)
}
 
let result = []
function findMaxConcat(tree) {
    let tmp = ''
    if (tree.token === true) {
        tmp = tree.fullValue
    }
 
    let processed = false
    for (let leaf of tree.leaves) {
        if (tmp !== '' && processed === false && leaf.value < tree.value) {
            result.push(tmp)
            processed = true
        }
        findMaxConcat(leaf)
    }
 
    if (tmp !== '' && processed === false) {
        result.push(tmp)
    }
}
 
findMaxConcat(tree)
console.log(result.join('.'))

Добавлено через 14 минут
хотя тогда на [9, 93, 993] сломается

Добавлено через 3 часа 40 минут
И надеюсь что уже точно рабочий вариант

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
let numbers = [9, 93, 993, 986, 50, 9869, 98699, 98698, 99, 989]
numbers = numbers.map(n => n.toString()).sort().reverse()
 
let tree = {
    value: null,
    token: null,
    leaves: []
};
 
function putNumberIntoTree(tree, number, prefix = '') {
    let size = number.length
    let ch = number.charAt(0)
    let found = false
 
    for (var leaf of tree.leaves) {
        if (leaf.value === ch) {
            found = true
            leaf.token = size === 1 ? prefix + ch : null
            break
        }
    }
 
    if (!found) {
        leaf = {
            value: ch,
            token: size === 1 ? prefix + ch : null,
            leaves: []
        }
        tree.leaves.push(leaf)
    }
 
    if (size === 1) {
        return
    }
 
    putNumberIntoTree(leaf, number.substr(1), prefix + ch)
}
 
for (let num of numbers) {
    putNumberIntoTree(tree, num)
}
 
Array.prototype.top = function() {
    return this.length === 0 ? -1 : this[this.length - 1]
}
 
let result = []
let stack = []
function findMaxConcat(tree) {
    while (stack.top().value > tree.value) {
        result.push(stack.pop().token)
    }
 
    if (tree.token !== null) {
        if (tree.leaves.length === 0) {
            result.push(tree.token)
        } else {
            stack.push(tree)
        }
    }
 
    for (let leaf of tree.leaves) {
        findMaxConcat(leaf)
    }
 
    if (stack.top() === tree) {
        result.push(stack.pop().token)
    }
}
 
findMaxConcat(tree)
console.log(result.join('.'))

@j2FunOnly · 16.05.2018, 15:12

Если бы числа были одинаковой длины, то входной массив сортируется в обратном порядке. Тут всё просто.

JavaScript
1
2
3
function compare (a, b) {
  return b - a;
}

Значит нам надо придумать хитрую функцию сравнивания чисел, в которой, к примеру (меньшее ставится вперед):

3 > 43 => 433 > 343
3 < 23 => 323 > 233
3 == 33 => 333 == 333
4242 == 424242 => 42 424 242 == 42 424 242
4242 < 4242399 => 42 424 242 399 > 42 423 994 242
423 > 4234392 => 4 234 392 423 > 4 234 234 392

Не ищем лёгких путей - не будем приводить числа к строке и пользоваться строковыми функциями.

Надо научиться считать цифры в числах:

JavaScript
1
2
3
4
5
6
7
8
9
10
var app = {};
 
app.digits = function digits (n) {
  var count = 1;
 
  n = n / 10;
  if (n >= 1) count += digits(n);
 
  return count;
}

Так как числа разной длины, можно сравнивать "кусочками" длинной короткого числа. Для этого надо брать первые n чисел длинного числа, заодно пусть возвращает и остаток:

JavaScript
1
2
3
4
5
6
7
8
9
app.firstDigits = function (n, count) {
  var digits = app.digits(n),
    divider = Math.pow(10, digits - count);
 
  return [
    Math.floor(n / divider),
    n % divider
  ]
}

Функция, которая из двух чисел возвращает числа одинаковой длины и "хвостик" длинного числа

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
app.normalizeLength = function (a, b) {
  var al = app.digits(a),
    bl = app.digits(b),
    numbers;
 
  if (al > bl) {
    numbers = app.firstDigits(a, bl);
    return [numbers[0], b, numbers[1]]
  } else {
    numbers = app.firstDigits(b, al);
    return [a, numbers[0], numbers[1]]
  }
}

Функция "сравниватель". Если числа a и b одинаковой длины возвращаем b - a, иначе от "длинного" числа берем часть равную длине "короткого" и сравниваем их, если и тут числа одинаковы, то сравниваем остаток длинного с коротким и т. д.

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
app.compare = function compare (a, b) {
  var al = app.digits(a),
    bl = app.digits(b);
 
  if (al === bl) {
    return b - a;
  } else {
    var numbers = app.normalizeLength(a, b),
      result = numbers[1] - numbers[0];
 
    if (result !== 0) return result;
 
    return compare(al < bl ? a : numbers[2], al < bl ? numbers[2] : b) // looks cryptic :/
  }
}

Осталось подсунуть в сортировку

JavaScript
1
2
3
app.maxNumber = function (arr) {
  return arr.slice().sort(app.compare);
}

HTML5
1
2
3
4
5
6
<form id="test-form">
  <label for="user-input">Введите числа, разделенные пробелом</label>
  <input name="userInput" id="user-input" type="text">
  <input type="submit">
  <output name="result"></output>
</form>

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
window.addEventListener('DOMContentLoaded', function() {
  document.querySelector('form#test-form').addEventListener('submit', function(e) {
    e.preventDefault();
 
    var p = document.createElement('p'),
      arr = this.userInput.value.split(' ').map(function(v) {
        return parseInt(v, 10);
      });
 
    p.textContent = app.maxNumber(arr).join('.');
    this.reset();
    this.result.appendChild(p);
  });
});

https://jsfiddle.net/j2FunOnly/4rjgy3zn/

Добавлено через 1 час 27 минут

Сообщение от Jewbacabra

И надеюсь что уже точно рабочий вариант

JavaScript
1
2
3
4
let numbers = [423, 4234392];
...
findMaxConcat(tree)
console.log(result.join('.')) //=> 423.4234392 < 4234392.423

JavaScript
1
2
3
4
let numbers = [33, 333, 33, 3];
...
findMaxConcat(tree)
console.log(result.join('.')) //=> 333.33.3 < 33.333.33.3

Новые блоги и статьи Все статьи Все блоги /
Валидация и контроль данных табличной части документа перед записью Maks 22.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в КА2. Задача: контроль и валидация данных табличной части документа перед записью с учетом регламента компании. . .	Отчёт о затраченных материалах за определенный период с макетом печатной формы Maks 21.04.2026 Отчёт из решения ниже размещён в конфигурации КА2. Задача: разработка отчёта по затраченным материалам за определённый период, с возможностью вывода печатной формы отчёта с шапкой и подвалом. В. . .	Отчёт о спецтехнике находящейся в ремонте Maks 20.04.2026 Отчёт из решения ниже размещен в конфигурации КА2. Задача: отобразить спецтехнику, которая на данный момент находится в ремонте. Есть нетиповой документ "Заявка на ремонт спецтехники" который. . .	Памятка для бота и "визитка" для читателей "Semantic Universe Layer (Слой семантической вселенной)" Hrethgir 19.04.2026 Сгенерировано для краткого описания по случаю сборки и компиляции скелета серверного приложения. И пусть после этого скажут, что статьи сгенерированные AI - туфта и не интересно. И это не реклама -. . .
Запрет удаления строк ТЧ документа при определённом условии Maks 19.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "Аккумуляторы", разработанного в конфигурации КА2. У данного документа есть ТЧ, в которой в зависимости от прав доступа. . .	Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .

@zlaskus 0 / 0 / 0 Регистрация: 26.02.2018 Сообщений: 6

	Найти наибольшую комбинацию числ 15.05.2018, 14:30. Показов 1134. Ответов 5 Метки нет (Все метки) На вход дается массив случайных чисел случайной длины, вводимый пользователем. Необходимо из этих чисел составить наибольшую комбинацию и ввести пользователю. Например если вбиты числа 9, 93, 986, 50 на выходе будет 9.986.93.50. Пожалуйста, помогите решить эту задачу. 0

@kalabuni супермизантроп 3941 / 2979 / 692 Регистрация: 18.04.2012 Сообщений: 8,629
	15.05.2018, 14:51
	расшифруйте понятие "наибольшая" почему наибольшей вы указали 9.986.93.50., а не 986.93.50.9. и не 93.986.50.9.? и что именно, и куда надо ввести пользователю? 0

@zlaskus 0 / 0 / 0 Регистрация: 26.02.2018 Сообщений: 6
	15.05.2018, 15:13 [ТС]
	Извините, опечатался. Число, которое образуется последовательностью 9.986.93.50 (число 99869350), больше других чисел, образованных другими комбинациями. Вывести пользователю нужно наибольшее получившееся число. На вход пользователь дает числа которые сам пожелает. Ограничений по количеству чисел или размеру нет. 0