Включение и принцип исключения в Java
Привет, я хочу, чтобы код включения и исключения принципала в Java.
Я хочу написать код для этой проблемы
Учитывая N простых чисел и число M, выясните, сколько чисел от 1 до M делится на любое из N заданных простых чисел.
The number of integers between 1 and 500 (both inclusive) that are divisible by 3 or 5 or 7 is
P(3 U 5 U 7) = P(3) + P(5) + P(7) - P(3X5) - P(5X7)- P(3X7)+ P(3X5X7)
P(3) = 500/3 = 166.66 Take 166 ,
P(5) = 500/5 = 100 ,
P(7) = 500/7 = 71.42 Take 71,
P(3X5) = p(15) = 500/15 = 33.33 Take 33 ,
P(7X5) = p(35) = 500/35 = 14.28 Take 14,
P(3X7) = p(21) = 500/21 = 23.8 Take 23,
P(3X5x7) = p(105 ) = 500/105 = 4.76 Take 4Answer = 166+100+71-33-14-23+4 = 271
Я пытаюсь построить код Java, используя эту реализацию C ++ https://www.geeksforgeeks.org/inclusion-exclusion-principle-and-programming-applications/
int count(int a[], int m, int n)
{
int odd = 0, even = 0;
int counter, i, j, p = 1;
int pow_set_size = (1 << n);//this for loop will run 2^n time
for (counter = 1; counter < pow_set_size; counter++) {
//I am not understanding below for loop code
p = 1;
for (j = 0; j < n; j++) {
/* Check if jth bit in the counter is set
If set then pront jth element from set */
if (counter & (1 << j)) {
p *= a[j];
}
}
// if set bits is odd, then add to
// the number of multiples
if (__builtin_popcount(counter) & 1)
odd += (100 / p);
else
even += 100 / p;
}
return odd - even;
}
Я просто не понимаю, что на самом деле делает этот цикл
for (j = 0; j < n; j++) {
/* Check if jth bit in the counter is set
If set then pront jth element from set */
if (counter & (1 << j)) {
p *= a[j];
}
}
и эта часть
// if set bits is odd, then add to
// the number of multiples
if (__builtin_popcount(counter) & 1)
odd += (100 / p);
else
even += 100 / p;
данное объяснение, которое я не понимаю
Числа, которые образованы умножением нечетного числа
будут добавлены простые числа и числа, образованные умножением
таким образом, четные числа будут вычтены, чтобы получить общее количество
кратно в диапазоне от 1 до М.
Пожалуйста, кто-нибудь может помочь мне с этой логикой реализовать его в Java?
Заранее спасибо 🙂
Решение
Внешний цикл используется для генерации всех возможных подмножеств простых факторов из входного массива. Каждый бит в counter представляет позицию в массиве.
Внутренний цикл проверяет каждый бит в counter, если бит установлен, он умножает соответствующее простое число из массива на pпроизведение всех простых факторов на проверяемое подмножество. Например, учитывая массив простых чисел {3, 5, 7}:
counter bits factors product
1 001 a[0] 3
2 010 a[1] 5
3 011 a[0] * a[1] 15
4 100 a[2] 7
5 101 a[0] * a[2] 21
6 110 a[1] * a[2] 35
7 111 a[0] * a[1] * a[2] 105
C ++ встроенный __builtin_popcount(counter) считает количество установленных бит в counter, Java-эквивалент Integer.bitCount(), Он используется для проверки, включен ли ряд факторов в p является нечетным (если это так, то младший бит результата будет установлен … это можно проверить другими способами, например, if (Integer.bitCount(counter) % 2 == 1)).
Наконец, количество кратных p меньше, чем m (500 в вашем случае) рассчитывается и добавляется к набору включений, если число факторов в p нечетный, или набор исключений, если он четный.
Обратите внимание, что в примере C ++ есть ошибка, она игнорирует m параметр и использует жестко закодированное значение 100,
В Java:
public class IncExc {
public static void main(String[] args) {
int a[] = {3, 5, 7};
int m = 500;
System.out.println(count(a, m));
}
static int count(int a[], int m) {
int odd = 0;
int even = 0;
int powSetSize = 1 << a.length;
// For all sub-sets of elements in the array of primes
for (int counter = 1; counter < powSetSize; counter++) {
int p = 1;
for (int j = 0; j < a.length; j++) {
// If the jth bit of this combination is set then multiply in the jth element
if ((counter & (1 << j)) != 0) {
p *= a[j];
}
}
// If the number of factors in p is odd, accumulate the count of multiples in our "odd" register
// Otherwise use the "even" register
if ((Integer.bitCount(counter) & 1) == 1)
odd += m / p;
else
even += m / p;
}
return odd - even;
}
}
Другие решения
Других решений пока нет …
detector