Xác định một số chia hết cho 3 mà không sử dụng + - * / %

#1
  • Tình hình là em có 1 vấn đề nhó nhỏ : Em muốn xác định 1 số chia hết cho 3 mà không được sử dụng các phép toán + , - * , : , div , mod , chỉ được dùng các toán tử so sánh . Bác nào biết chỉ giúp em với ạ :slight_smile: !
#2
3 Likes
#3 
cout << "Số " << x << " có chia hết cho 3 hay ko? ";
cin >> answer;

2 dòng thôi nhá :heart_eyes:

2 Likes
#4

Hỏi ngoài luồng nhưng : Làm vậy để làm gì ? Sợ một ngày nào đó CPU không có khả năng thực hiện ±*/ ???

2 Likes
#5

Để chứng tỏ tư’ss duy’ss bản thân trong các bài tập hay cuộc thi sanh dziên giỏi cấp tểnh và quớt dza :">

4 Likes
#6

Bác vui tính quá :))

#7

Chỉ biết cách mà chương trình nó biên dịch bác ạ chứ ngoài ra ai lại rảnh để thực hiện 1 cái đơn giản để biến thanh phức tạp vậy

#8

Cái này làm gì như bác suy nghĩ đâu @@

#9

Biết cách chương trình nó biên dịch thì xem trong listing của nó để thấy mã ASM hoặc dịch ngược file thực thi.

1 Like
#10

đây nhé, đáp án ở bên stackoverflow kia tủi loz :triumph:

#include <iostream>
#include <cassert>

void increment(long long& n)
{
    long long i = 1;
    for (int k = n; k & 1; k >>= 1, n &= ~i, i <<= 1);
    n |= i;
}

bool divisibleBy3(int n)
{
    if (!n) return true;
    if (n < 0) return divisibleBy3(-n);
    bool a = 0, b = 1; //00 = 10 = 0, 01 = 1, 11 = -1
    for (long long i = 1; i != n; )
    {
        i <<= 1;
        a = !a;
        if (i > n)
        {
            i >>= 1;
            increment(i);
            if (!b) { a = 0; b = 1; } else if (!a) b = 0;
        }
    }
    return !b;
}

int main()
{
    for (int i = -10000; i <= 10000; ++i)
        assert(divisibleBy3(i) == (i%3 == 0));
}

hehe chạy chậm như rùa bò :joy:

bắt đầu với i = 1, nhân 2 tới khi nào > n thì chia 2 lại và cộng 1 vào i, rồi cứ thế tới khi nào i == n thì dừng. ab là số dư trong phép chia i cho n. Nếu i chia n dư 1 thì i2 chia n sẽ dư -1, nếu i chia n dư -1 thì i2 chia n sẽ dư 1. Cứ thế mà phang :joy: chỉ cần 1 phép toán increment.

3 Likes
#11

Mình đùa mà, nhạy cảm ghê :joy:

1 Like
#13

:grin::grin::grin: em có nói g căng đâu bác haha

#14

Thank bác haha . Em phải tìm hiểu nhiều mới được :))

#15

Haha vấn đề ở đâu k phải xem đoạn complie mà là để em hiểu sâu về ngôn ngữ lập trình ý

#17

Hiểu sâu cứ ASM là chuẩn :stuck_out_tongue:

1 Like
#18

2^(2k) chia 3 dư 1
2^(2k+1) chia 3 dư 2

Code có sử dụng hàm +1 trá hình, đơn giản hơn code của anh @tntxtnt 1 tí =))

UPD: Thêm trường hợp check số âm.

#include <iostream>
#include <bitset>
using namespace std;

typedef long long ll;

ll n;

int add1(int k) {
	if (k & 1) { // odd
		return (add1(k >> 1) << 1);
	} else { // even
		return (k | 1);
	}
}

bool check(ll n) {
	if (n < 0)
		return check(abs(n));
	if (n == 0 || n == 3)
		return true;
	if (n == 1 || n == 2)
		return false;

	bool odd = true;
	int s = 0;
	for (ll k=1; k<=n; k <<= 1) {
		odd = !odd;
		if (n & k) {
			if (odd) { // 2^(2x+1) mod 3 == 2
				s = add1(s);
				s = add1(s);
			} else // 2^(2x) mod 3 == 1
				s = add1(s);
		}
	}
	return check(s);
}

int main() {
	/*
	for (int n=0; n<100000; n++) { // TEST
		// cout << n << " is " << (check(n) ? "" : "not ") << "divisible by 3\n";
		// if ((n % 3 == 0) != check(n)) 
		//	cout << "ERROR: " << n << endl;
	}
	*/
	cin >> n;
	cout << n << " is " << (check(n) ? "" : "not ") << "divisible by 3\n";
}
2 Likes
#19

cách đơn giản hơn, “1 dòng” thôi :joy:

bool divisibleBy3(int n, int rem=0)
{
    static int nextSub[][3] = { {0, 1, 2}, {2, 0, 1} };
    static int nextDiv2[] = {0, 2, 1};
    if (n < 0) return divisibleBy3(~n, 2);
    for (; n; n >>= 1) rem = nextDiv2[nextSub[n&1][rem]]; //1 dòng
    return !rem;
}
3 Likes
#20

Cho phép em chơi xấu tí =))

def check(n):
	s1 = []
	s2 = []
	for c in n:
		if c in '147':
			s1.append(c)
		elif c in '258':
			s2.append(c)
	
	return len(s1) == len(s2)


n = int(input())
print("" if check(str(abs(n))) is True else "not ", "divisible by 3", sep='')
2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?