두 개의 연속적인 1 또는 3 개의 연속 적인 0으로 구성되지 않는 비트 문자열의 수를 계산하고 싶습니다.
하지만 둘 다 아닙니다
나는 두 개의 연속적인 것 또는 3 개의 연속 적인 0으로 구성된 알고리즘을 찾았 지만 그것을 제외하고 싶기 때문에 그들 사이의 교차점을 찾지 못했습니다 ..
예를 들어, 내 입력은 4입니다. 3 개의 연속 0 또는 2 개의 연속 1이없는 4 비트 길이 시퀀스를 모두 찾아야합니다. 따라서 답은 7:00, 0100, 0101, 1001 및 1010이됩니다.
어떤 아이디어? 감사..
다음 접근 방식을 사용할 수 있습니다.
1...이면 하위 시퀀스는 0.00...하위 시퀀스는 1.0또는로 시작할 수 있습니다 1.나머지는 프로그램에서 명확해야합니다.
public class BitSequences {
public static void main(String[] args) {
for (int i = 0; i <= 64; ++i) {
System.out.println(i + " " + bitSequences(i));
}
}
public static long bitSequences(int length) {
return bitSequences(length, Bit.NONE, Bit.NONE);
}
public static long bitSequences(int length, Bit prePreBit, Bit preBit) {
if (length <= 0) {
return 1;
} else if (preBit == Bit.ONE) {
return bitSequences(length - 1, preBit, Bit.ZERO);
} else if (prePreBit == Bit.ZERO && prePreBit == Bit.ZERO) {
return bitSequences(length - 1, preBit, Bit.ONE);
}
return bitSequences(length - 1, preBit, Bit.ONE)
+ bitSequences(length - 1, preBit, Bit.ZERO);
}
enum Bit {
ZERO,
ONE,
NONE
}
}
동적 프로그래밍을 사용하여 프로그램을 개선 할 수 있지만 귀하의 경우에는 중요하지 않을 수 있습니다. 에 대한 계산 length = 64은 1 초 안에 완료됩니다. 결과 : 109'870'576 (대략 2있다 (28) 이없는 길이 64) 비트 문자열 11또는 000그들에가.
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다