(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;
}
|
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 количество;
}
|
Спасибо большое! Вот только мне надо, чтобы был использован ассоциативный массив
|
Цитата:
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 количество;
}
|
1.Я правильно понимаю, new Map() - это создание ассоциативного массива?
2. И так как мне нужны нечетные разряды, то в условии будет так: if (i % 2 === 1) ? 3. Еще в HTML-страничке долго выводится ответ, а для больших M (начиная с 10) и вовсе "страница не отвечает". Из-за чего это может быть? |
:write: может быстрее подсчитать количество комбинаций нужной суммы исходя из количества мест нечётных и умножить на комбинацию чётных чисел?
|
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));
|
Цитата:
Например, при М = 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) Далее цикл поменять на более эффективный перебор сумм, позже напишу если время будет |
Цитата:
|
Цитата:
|
| Часовой пояс GMT +3, время: 10:27. |