숫자가 3으로 나눌 수 있는지 확인하십시오 [폐쇄
https://stackoverflow.com/questions/844867
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
숫자가 3으로 나눌 수 있는지 판단하기 위해 코드를 작성합니다. 함수에 대한 입력은 하나의 지금까지 수신 된 숫자가 3으로 나눌 수있는 숫자의 이진 표현, 그렇지 않으면 0이되면 비트, 0 또는 1, 출력은 1이어야합니다.
예 :
input "0": (0) output 1
inputs "1,0,0": (4) output 0
inputs "1,1,0,0": (6) output 1
이것은 인터뷰 질문을 기반으로합니다. 나는 논리 게이트의 그림을 요구하지만 이것은 stackoverflow이기 때문에 코딩 언어를 받아 들일 것입니다. 하드웨어 구현 (Verilog 등)의 보너스 포인트.
파트 A (쉬운) : 첫 번째 입력은 MSB입니다.
파트 B (조금 더 힘들어) : 첫 번째 입력은 LSB입니다.
파트 C (어려운) : 어느 것이 더 빠르고 작습니다 (a) 또는 (b)? (이론적으로는 큰 의미에서는 아니지만 실질적으로 더 빠르거나 작습니다.) 이제 느리게/더 큰 것을 가져 가서 더 빠르거나 작은 것만 큼 빠르거나 작게 만듭니다.
해결책
heh
LSB의 상태 테이블 :
S I S' O
0 0 0 1
0 1 1 0
1 0 2 0
1 1 0 1
2 0 1 0
2 1 2 0
설명 : 0은 3으로 나눌 수 있습니다. 0 << 1 + 0 = 0. 사용을 반복하십시오 S = (S << 1 + I) % 3 그리고 O = 1 만약에 S == 0.
MSB의 상태 테이블 :
S I S' O
0 0 0 1
0 1 2 0
1 0 1 0
1 1 0 1
2 0 2 0
2 1 1 0
설명 : 0은 3으로 나눌 수 있습니다. 0 >> 1 + 0 = 0. 사용을 반복하십시오 S = (S >> 1 + I) % 3 그리고 O = 1 만약에 S == 0.
S' 위와 다르지만 O는 동일하게 작동합니다. S' 동일한 경우 (00 및 11)의 경우 0입니다. 두 경우 모두 O_LSB = O_MSB에서 O가 동일하므로 MSB를 LSB만큼 짧게하거나 그 반대로 MSB를 사용하려면 두 가지 중 가장 짧은 것을 사용하십시오.
다른 팁
소수점 자리를 번갈아 가서 빼서 숫자가 11의 배수인지 여부를 결정하는 데 상당히 잘 알려진 트릭이 있습니다. 끝에있는 숫자가 11의 배수라면, 당신이 시작한 숫자는 또한 11의 배수입니다.
47278 4 - 7 + 2 - 7 + 8 = 0, multiple of 11 (47278 = 11 * 4298) 52214 5 - 2 + 2 - 1 + 4 = 8, not multiple of 11 (52214 = 11 * 4746 + 8)
이진 번호에 동일한 트릭을 적용 할 수 있습니다. 이진수는 비트의 교대 합이 3의 다중 인 경우에만 3의 배수입니다.
4 = 100 1 - 0 + 0 = 1, not multiple of 3 6 = 110 1 - 1 + 0 = 0, multiple of 3 78 = 1001110 1 - 0 + 0 - 1 + 1 - 1 + 0 = 0, multiple of 3 109 = 1101101 1 - 1 + 0 - 1 + 1 - 0 + 1 = 1, not multiple of 3
MSB 또는 LSB로 시작하든 차이가 없으므로 다음 Python 기능은 두 경우 모두 똑같이 잘 작동합니다. 한 번에 하나씩 비트를 반환하는 반복기가 필요합니다. multiplier 음수의 모듈로 복용을 피하기 위해 1과 -1 대신 1과 2 사이의 번갈아 가며.
def divisibleBy3(iterator):
multiplier = 1
accumulator = 0
for bit in iterator:
accumulator = (accumulator + bit * multiplier) % 3
multiplier = 3 - multiplier
return accumulator == 0
여기 ... 새로운 것 ... 길이의 이진수 (수천 자리조차도)가 3으로 나눌 수 있는지 확인하는 방법.
-->((0))<---1--->()<---0--->(1) ASCII representation of graph
사진에서.
- 당신은 더블 원에서 시작합니다.
- 하나 또는 0을 얻으면 숫자가 원 안에 있으면 그 원 안에 머무 릅니다. 그러나 숫자가 줄에 있으면 줄을 가로 질러 이동합니다.
- 모든 숫자가 혼란 스러울 때까지 2 단계를 반복하십시오.
- 마침내 이중 원으로 끝나면 이진수는 3으로 나눌 수 있습니다.
또한 3으로 나눌 수있는 숫자를 생성하는 데 이것을 사용할 수 있습니다. 그리고 이미지를 회로로 변환하는 것은 어렵지 않을 것입니다.
1 그래프 사용 예 ...
110000000000000101111111111111111은 3으로 나눌 수 있습니다 (이중 원으로 다시 끝납니다)
직접 시도해보십시오.
이진 숫자를 기본 10 숫자로 변환 할 때 모드 10을 수행하기위한 유사한 트릭을 수행 할 수도 있습니다. (10 개의 원, 각각은 두 배의 원을 입고 모듈로에서 발생하는 값 0에서 9를 나타냅니다)
편집하다: 이것은 왼쪽에서 오른쪽으로 실행되는 숫자를위한 것입니다. 그러나 역 언어를 받아들이도록 유한 상태 기계를 수정하는 것은 어렵지 않습니다.
노트: 그래프 ()의 ASCII 표현에서 단일 원을 나타내고 (())는 이중 원을 나타냅니다. 유한 상태 기계에서는 이들이 상태라고하며 이중 원은 수용 상태입니다 (상태는 결국 3으로 나눌 수 있음을 의미합니다)
다음은 손으로 할 수있는 간단한 방법입니다. 1 = 2 이후2 모드 3, 우리는 1 = 2를 얻습니다2n 모든 양의 정수에 대한 모드 3. 또한 2 = 22N+1 따라서 Mod 3. 따라서 홀수 비트 위치에서 1 비트를 계산하여 정수가 3만큼 나눌 수 있는지 확인할 수 있습니다.이 숫자에 2를 곱하고 1 비트의 1 비트 수를 결과에 추가하고 확인하십시오. 결과는 3으로 나눌 수 있습니다.
예 : 5710=1110012. 홀수 위치에는 2 비트가 있고 짝수 위치에는 2 비트가 있습니다. 2*2 + 2 = 6은 3으로 나눌 수 있습니다. 따라서 57은 3으로 나눌 수 있습니다.
질문 c)를 해결하려는 생각도 다음과 같습니다. 이진 정수의 비트 순서를 반전하면 모든 비트는 짝수/홀수 위치 또는 모든 비트가 변경됩니다. 따라서 정수 n 결과의 비트의 순서를 반전시키는 것은 n이 3으로 나눌 수있는 경우에만 3으로 나눌 수있는 정수입니다. 따라서 질문 a) 질문 b에 대한 모든 해결책은 질문 b에 대한 변경 사항이없고 그 반대도 마찬가지입니다. 흠, 아마도 이것은 어떤 접근법이 더 빠른지 알아내는 데 도움이 될 수 있습니다 ...
산술 모듈로 3을 사용하여 모든 계산을 수행해야합니다. 이것이 방법입니다.
MSB :
number=0
while(!eof)
n=input()
number=(number *2 + n) mod 3
if(number == 0)
print divisible
LSB :
number = 0;
multiplier = 1;
while(!eof)
n=input()
number = (number + multiplier * n) mod 3
multiplier = (multiplier * 2) mod 3
if(number == 0)
print divisible
이것은 일반적인 아이디어입니다 ...
자, 당신의 역할은 이해하는 것입니다 왜 이것은 정확합니다.
그리고 네, 스스로 숙제를하십시오;)
아이디어는 숫자가 임의로 길어질 수 있다는 것입니다. mod 3 여기서, 당신의 숫자는 당신의 정수 클래스의 용량을 넘어서 자라기 때문입니다.
아이디어는 숫자에 무슨 일이 일어나는지 알아 차리는 것입니다. 오른쪽에 비트를 추가하는 경우 실제로하고있는 일은 왼쪽으로 왼쪽으로 이동하고 새로운 비트를 추가하는 것입니다.
Shift-left는 2를 곱하는 것과 동일하며 새 비트를 추가하면 0 또는 1을 추가합니다. 0부터 시작했다고 가정하면 마지막 숫자의 모듈로 -3을 기반으로 재귀 적으로 수행 할 수 있습니다.
last | input || next | example
------------------------------------
0 | 0 || 0 | 0 * 2 + 0 = 0
0 | 1 || 1 | 0 * 2 + 1 = 1
1 | 0 || 2 | 1 * 2 + 0 = 2
1 | 1 || 0 | 1 * 2 + 1 = 0 (= 3 mod 3)
2 | 0 || 1 | 2 * 2 + 0 = 1 (= 4 mod 3)
2 | 1 || 2 | 2 * 2 + 1 = 2 (= 5 mod 3)
이제 왼쪽에 조금 추가 할 때 어떻게되는지 보자. 먼저 주목하십시오.
22n 모드 3 = 1
그리고
22N+1 모드 3 = 2
이제 현재 반복이 홀수인지 균일한지에 따라 모드에 1 또는 2를 추가해야합니다.
last | n is even? | input || next | example
-------------------------------------------
d/c | don't care | 0 || last | last + 0*2^n = last
0 | yes | 1 || 0 | 0 + 1*2^n = 1 (= 2^n mod 3)
0 | no | 1 || 0 | 0 + 1*2^n = 2 (= 2^n mod 3)
1 | yes | 1 || 0 | 1 + 1*2^n = 2
1 | no | 1 || 0 | 1 + 1*2^n = 0 (= 3 mod 3)
1 | yes | 1 || 0 | 2 + 1*2^n = 0
1 | no | 1 || 0 | 2 + 1*2^n = 1
input "0": (0) output 1
inputs "1,0,0": (4) output 0
inputs "1,1,0,0": (6) output 1
이 마지막 입력이되어서는 안됩니다 12, 아니면 질문을 오해하고 있습니까?
실제로 LSB 방법은 실제로이를 더 쉽게 만듭니다. C :
MSB 방법 :
/*
Returns 1 if divisble by 3, otherwise 0
Note: It is assumed 'input' format is valid
*/
int is_divisible_by_3_msb(char *input) {
unsigned value = 0;
char *p = input;
if (*p == '1') {
value &= 1;
}
p++;
while (*p) {
if (*p != ',') {
value <<= 1;
if (*p == '1') {
ret &= 1;
}
}
p++;
}
return (value % 3 == 0) ? 1 : 0;
}
LSB 방법 :
/*
Returns 1 if divisble by 3, otherwise 0
Note: It is assumed 'input' format is valid
*/
int is_divisible_by_3_lsb(char *input) {
unsigned value = 0;
unsigned mask = 1;
char *p = input;
while (*p) {
if (*p != ',') {
if (*p == '1') {
value &= mask;
}
mask <<= 1;
}
p++;
}
return (value % 3 == 0) ? 1 : 0;
}
개인적으로 나는 이것들 중 하나가 다른 것과 크게 다를 것이라고 믿는 데 어려움을 겪고 있습니다.
나는 Nathan Fellman이 Part A와 B에 적합한 길을 가고 있다고 생각합니다 (B는 추가 상태가 필요합니다. 숫자 위치가 홀수인지 짝수인지 추적해야합니다).
나 생각한다 파트 C의 트릭은 last 각 단계에서 가치. IE 0은 0으로 이동하고 1은 2로, 2는 1로갑니다.
숫자의 합이 3으로 나눌 수있는 경우 숫자는 3으로 나눌 수 있습니다.
숫자를 추가하고 합계를 얻을 수 있습니다.
- 합계가 10이면 동일한 방법을 사용합니다.
- 3, 6, 9라면 분할 가능합니다.
- 합계가 3, 6, 9와 다르면 나눌 수 없습니다.
