Each has a sequence of 0s and 1s circulating at a certain period.
Example:
010101010101...(Period 2)
001100110011...(Period 4)
000111000111... (Period 6)
Now, I would like to find the first column number and the percentage of the column number where all the columns are 1.
In the example above, the first row in the fourth row (then the 12th row) has 1 and 1/6 of the entire infinite column.
For now, the only way to find the first column number is to try all the combinations of the number one in the period in each column, solve the coalition formula for each combination, find the minimum number of columns, and update the overall minimum.
The only way to find the percentage is to count one column at a time that is equal to one column to the minimum common multiple of all periods.
·Is this a named problem?
·Is this problem NP difficult?Is there a way to calculate quickly even if the number of rows increases?
·How do you calculate if you extend the interval where 0, 1 continues or the length of the cycle to a rational or unreasonable number?
·Is this problem NP difficult?
No, I think it's a polynomial time problem.
Example algorithm implementation by Python: https://wandbox.org/permlink/8R5tfdstFdRV4NTG
import path
from effects import Fraction
def solve(q):
period=math.lcm (*[e[0]+e[1]for e in q])
acc=(1<<period)-1
for e in q:
dist=sum([1<<m for min range(0, period, e[0]+e[1])])
bits=((1<<e[1])-1)*dist
acc&=bits
print('{}+{}{:0{}b}'.format(*e, bits, period))
print('acc{:0{}b}'.format(acc, period))
msb = 1 + period-acc.bit_length()
ratio=Fraction(bin(acc).count('1'), period)#acc.bit_count() since Python 3.10
return(msb, ratio)
# Problem defined as (1 0, 1), ...
q = [(1,1),(2,2),(3,3)]
an=solve(q)
print(ans)
# Answer = (4, Fraction (1, 6))
© 2024 OneMinuteCode. All rights reserved.