Javascript-форум (https://javascript.ru/forum/)
-   Общие вопросы Javascript (https://javascript.ru/forum/misc/)
-   -   (JavaScript) Нужно найти количество чисел, у которых сумма цифр, равна данному числу (https://javascript.ru/forum/misc/77482-javascript-nuzhno-najjti-kolichestvo-chisel-u-kotorykh-summa-cifr-ravna-dannomu-chislu.html)

ProgYoung 11.05.2019 21:38
(JavaScript) Нужно найти количество чисел, у которых сумма цифр, равна данному числу
 
Задача такая: определить количество М-значных натуральных чисел, у которых сумма цифр, стоящих в нечетных разрядах, равна N (1<N<90, 5<M<20)

Я решаю ее таким образом: например, M=5 => рассматриваем отрезок [10000;99999]. Каждое число перевожу в строковый тип, разбиваю на цифры и заношу в ассоциативный массив. При этом с помощью .shift удаляю 0-ой элемент, передвигая строку. Далее нахожу нечетный разряд и сравниваю с числом N.

Проблема в том, что я видимо не правильно заношу в массив, но как исправить, без понятия. Объясните, пожалуйста!

function calculation(M,N){
  for (var k=Math.pow(10,M-1);k<=Math.pow(10,M)-1;k++){
   var chisla = [];
   K = String(k);
   for (var i=1;i<=M;i++){
     chisla[String(i)] = K[0];
     K = chisla.shift();
   }
   var sum = 0;
   for (i=1;i<=M;i++){
    if (i%2==1){
     sum = sum+Number(chisla[String(i)]);
    }
   }
   if (sum==N){
    kol=kol+1;
   }
  }
  return kol;
 }

Malleys 11.05.2019 22:47 
function calculation(M,N){
	var kol = 0;
	for(var k = Math.pow(10, M - 1); k <= Math.pow(10, M) - 1; k++){
		var chisla = Array.from(String(k)).reverse();

		var sum = 0;
		for(var i = 0; i < M; i++) {
			if (i % 2 === 0) {
				sum += Number(chisla[i]);
			}
		}
		if(sum === N) kol++;
	}
	return kol;
}


UPD Можно использовать методы массива, и также использовать кириллицу! 
function calculation(M, N){
	var количество = 0;
	for (var k = Math.pow(10, M - 1); k <= Math.pow(10, M) - 1; k++) {
		const сумма = Array.from(String(k)).reverse()
			.reduce((сумма, цифра, i) => i % 2 === 0 ? сумма + Number(цифра) : сумма, 0)
		;
		if(сумма === N) количество++;
	}
	return количество;
}

ProgYoung 11.05.2019 23:07
Спасибо большое! Вот только мне надо, чтобы был использован ассоциативный массив

Malleys 11.05.2019 23:24
Цитата:
Сообщение от ProgYoung
Вот только мне надо, чтобы был использован ассоциативный массив
 
function calculation(M,N){
	var количество = 0;
	for(var k = Math.pow(10, M - 1); k <= Math.pow(10, M) - 1; k++){
		const цифры = new Map();
		const число = String(k);

		for(var i = 0; i < M; i++) {
			цифры.set(M - 1 - i, число[i]);
		}

		var сумма = 0;
		for(var i = 0; i < M; i++) {
			if (i % 2 === 0) {
				сумма += Number(цифры.get(i));
			}
		}
		if(сумма === N) количество++;
	}
	return количество;
}

ProgYoung 12.05.2019 09:19
1.Я правильно понимаю, new Map() - это создание ассоциативного массива?
2. И так как мне нужны нечетные разряды, то в условии будет так: if (i % 2 === 1) ?
3. Еще в HTML-страничке долго выводится ответ, а для больших M (начиная с 10) и вовсе "страница не отвечает". Из-за чего это может быть?

рони 12.05.2019 10:37
:write: может быстрее подсчитать количество комбинаций нужной суммы исходя из количества мест нечётных и умножить на комбинацию чётных чисел?

рони 12.05.2019 10:51 
function calculation(M,N){
    var количество = 0;
    for(var k = Math.pow(10, M - 1); k <= Math.pow(10, M) - 1; k++){
        const цифры = new Map();
        const число = String(k);

        for(var i = 0; i < M; i++) {
            цифры.set(M - 1 - i, число[i]);
        }

        var сумма = 0;
        for(var i = 0; i < M; i++) {
            if (i % 2 === 0) {
                сумма += Number(цифры.get(i));
            }
        }
        if(сумма === N) количество++;
    }
    return количество;
}
M = 3, N = 5;
//нечётных мест 2
// комбинаций суммы без нуля в начале [[1,4],[2,3],[3,2],[4,1],[5,0]] всего 5
// чётных мест 1, комбинаций 10 (0 - 9)
// ответ в числах [100,999] где сумма нечётных равна 5 всего 5 * 10 = 50 вариантов
alert(calculation(M,N));

Alexandroppolus 12.05.2019 17:40
Цитата:
Сообщение от рони
может быстрее подсчитать количество комбинаций нужной суммы исходя из количества мест нечётных и умножить на комбинацию чётных чисел?
Это само собой. Для начала можно решить задачу "влоб", работая только с нечетными разрядами (предполагаем, что самый младший разряд - первый, т.е. нечетный):
Например, при М = 5
ХХХХХ считаем только красные (нечетные), проходя циклом от 100 до 999, потом домножаем на 10*10 вариантов черных (четных)

при М = 6 (ХХХХХХ) красные будут от 000 до 999, домножаем на 9*10*10

Итого:
цикл for (var i = A; i <= B; ++i)
A = M%2 ? Math.pow(10, Math.ceil(M / 2) - 1) : 0
B = Math.pow(10, Math.ceil(M / 2)) - 1
вариантов черных: C = M%2 ? Math.pow(10, Math.floor(M / 2)) : 9 * Math.pow(10, M / 2 - 1)


Далее цикл поменять на более эффективный перебор сумм, позже напишу если время будет

рони 12.05.2019 18:38
Цитата:
Сообщение от Alexandroppolus
при М = 6 (ХХХХХХ) красные будут от 000 до 999, домножаем на 9*10*10
почему 9?

Alexandroppolus 12.05.2019 21:01
Цитата:
Сообщение от рони
почему 9?
потому что в самом старшем разряде цифры 1...9, а не 0...9

рони 12.05.2019 21:14
Alexandroppolus,
почему при М = 6 у вас иной подсчёт, чем при М = 5?

рони 12.05.2019 21:57
Цитата:
Сообщение от Alexandroppolus
(предполагаем, что самый младший разряд - первый, т.е. нечетный):
 
function calculation(M,N){
    var количество = 0;
    for(var k = Math.pow(10, M - 1); k <= Math.pow(10, M) - 1; k++){
        const число = String(k);
        const цифры = [...число];
        var сумма = 0;
        for(var i = 0; i < M; i += 2) {
                сумма += +цифры[i];
        }
        if(сумма === N) количество++;
    }
    return количество;
}

alert(calculation(5,5) * 10 === calculation(6,5));

10!!! а не 9

рони 12.05.2019 22:04
Alexandroppolus,
:) не учёл что речь была о младшем разряде, считал первую цифру нечётной.
вопрос исчерпан.:thanks:

Alexandroppolus 12.05.2019 23:30
(1<N<90, 5<M<20)
поскольку при этих ограничениях результат не всегда влезает в Number.MAX_SAFE_INTEGER, то возвращаем его в виде строки :)

https://jsfiddle.net/bw783h4j/

рони 13.05.2019 00:39
Alexandroppolus,
ничего не понял, но спасибо! :)

ProgYoung 14.05.2019 18:10
Alexandroppolus,
Спасибо большое за ваш труд!
Не могли бы вы еще раз попроще объяснить, что происходит в функции sumCount() ?

Alexandroppolus 14.05.2019 18:32
ProgYoung,
функциия sumCount определяет, сколькими способами можно разложить число n на m слагаемых, так что каждое слагаемое будет в пределах от 0 до 9, а первое слагаемое - от f до 9. Она работает рекурсивно - в цикле перебирает все возможные значения первого слагаемого и на каждой итерации считает sumCount(m-1, n-i) - т.е. если первое число взять равным i, то сколько будет вариантов по остальным числам и оставшейся сумме. Это всё суммируется.

Массив saved - для сохранения значений sumCount(m, n), т.к. они часто будут повторяться: например, если первые два слагаемых равны (1, 7), (2, 6) и т.д., то оставшаяся сумма одинакова.

т.е. sumCount как раз и делает подсчет вариантов для нечетных разрядов, коих оказалось примерно половина от всех разрядов числа.

ProgYoung 14.05.2019 18:57
Alexandroppolus,
почему первое слагаемое от f, а не от 1? Еще у меня так и не выводит ответ, хотя вроде все правильно (я сохраняю текстовый документ, как .html и открываю в гугле):

<!DOCTYPE html>
<html>
<head>
 <META http-equiv="Content-Type" content="text/html; charset=windows-1251"/>
 <title></title>
</head>
<body>

<p>Введите число N - сумма чисел в нечетных разрядах:</p>
<input type="text" id="n" size="10" maxlength="15"/>
<p>Введите число M (M-значные числа):</p>
<input type="text" id="m" size="10" maxlength="15"/>
<p id="solution">Решение</p>
<p><textarea id="solve" rows="15" cols="40"></textarea></p>

<script type="text/javascript">

var calculation = function() {
    function sumCount(f, m, n, saved) {
        if (m < 2) {
            return n < 10 && n >= f ? 1 : 0;
        }
        if (n < 1) {
            return 1 - f;
        }
        if (saved[m][n] >= 0) {
            return saved[m][n];
        }
        var c = 0, last = Math.min(n, 9);
        for (var i = f; i <= last; ++i) {
            c += sumCount(0, m - 1, n - i, saved);
        }
        return saved[m][n] = c;
    }

    function calc(M, N) {
        var saved = [];
        var digs = Math.ceil(M / 2);
        for (var i = 0; i <= digs; ++i) {
            saved[i] = new Array(N + 1);
            for (var j = 0; j <= N; ++j) {
                saved[i][j] = -1;
            }
        }
        var count = sumCount(M % 2, digs, N, saved);
        var suf = Array(Math.ceil(M / 2)).join('0');
        var k = M % 2 ? 1 : 9;
        
        return count ? (count * k) + suf : '0';
    }

    return calc;
};

 document.getElementById("solution").onclick = function() {

   var M = parseInt(document.getElementById("id_m").value, 10);
   var N = parseInt(document.getElementById("id_n").value, 10);

   document.getElementById("solve").innerHTML = calculation(M, N);

 }
</script>
</body>
</html>

Alexandroppolus 14.05.2019 23:18
Цитата:
Сообщение от ProgYoung
почему первое слагаемое от f, а не от 1?
f по факту может быть 0 или 1, функция вызывается так: sumCount(M % 2, digs, N, saved);
Цитата:
Сообщение от ProgYoung
Еще у меня так и не выводит ответ, хотя вроде все правильно
id у элементов не совпадают с теми, которые в getElementById используются.

ProgYoung 15.05.2019 07:49
Alexandroppolus,
тьфу ты... Спасибо большое!)


Часовой пояс GMT +3, время: 01:56.