Tìm bội số nhỏ nhất của N chỉ chứa số 0 và 1

[toilathanh (Trần Duy Thanh)]

Chào mọi người, mình có bài tập của C, với đề là: viết chương trình tìm bội số nhỏ nhất của N chỉ chứa số 0 và 1 (hoặc toàn 1)
VD: N=2 , xuất ra 10; N=3 xuất ra 111
Mình cần ý tưởng thoi ạ, mong mọi người giúp đỡ

[rogp10]

Một số như trên có thể viết dưới dạng tổng các lũy thừa của 10

Bài này QHĐ mod n và chú ý yêu cầu khi truy vết.

[Le_Trong1 (Lê Trọng)]

Ý tưởng của tui: tạo một vòng lặp dò từng bội số của N, bất đầu từ N mỗi lần lặp + N vô cho tới khi tìm đc.

Number: 1234
Result: 11001110

[rogp10]

Số này có dạng thì phải từ dạng mà brute force chứ

[toilathanh (Trần Duy Thanh)]

Ý tưởng ban đầu tui cũng vậy, sau đó dùng cắt chuỗi để xét các phần tử có chứa đúng 0,1 hay không. Nhưng có vẻ không tối ưu lắm ấy?!

[Le_Trong1 (Lê Trọng)]

Tui cũng công nhận là không tối ưu thiệt, số càng lớn càng tốn thời gian, hoặc tìm những số là bội của 9 ít nhất phải 9 chữ số 1 trong đó.
Dùng cách này thử xem

    public static String find(ArrayList<String> list, int number) {
        ArrayList<String> newList = new ArrayList<>();
        for(int i = 0 ; i < list.size() ; i++) {
            if(Double.parseDouble(list.get(i)) % number == 0) return list.get(i);
            
            newList.add(list.get(i)+"0");
            newList.add(list.get(i)+"1");
        }
        return find(newList, number);
    }

[tntxtnt]

N giới hạn bao nhiêu?

1 = 10^0, chia N dư r_0
10 = 10^1, chia N dư r_1
100 = 10^2, chia N dư r_2
…
10^{n-1}, chia N dư r_{n-1}
tới đây ko cần tìm nữa vì số dư của 1 số chia N chỉ có N giá trị.

bài toán chuyển về 0-1 min knapsack (chứ ko phải max knapsack). Có N “món đồ”, “món đồ” thứ i có giá trị 10^i và “khối lượng” r_i. Tìm cách lấy “đồ” sao cho tổng khối lượng = N và giá trị thấp nhất :V

[Duy_Hoang98 (DS)]

cái này dùng vòng lặp từ 1 rồi lấy N x số lần lặp hiện tại kiểm tra có chứ số 1 hoặc 0 thì break rồi in ra kq là đc mà nhỉ !?

[rogp10]

2 lũy thừa N/2 chứ N đâu

[toilathanh (Trần Duy Thanh)]

Mình tìm thấy link này, mn xem thử:

How to find the smallest number with just 0 and 1 which is divided by a given number?

[rogp10]

Đã đọc dùng BFS cho đồ thị n đỉnh, chắc chắn ra được.

Vấn đề nằm ở trong câu if node in visited visited phải là set hay hash.

# pseudo
def bfs(n):
   q = [(1, null, 1)]
   visited = Set.new(key: &third)
   while not q.empty:
      q_new = []
      for v in q do # <-- reference
         if visited.add?(v): next
         rem = (v.third*10) % n
         case rem:
            when 0 then return trace(v, 0)
            when n-1 then return trace(v, 1)
            else q_new.push((0, v, rem)), q_new.push((1, v, rem+1))
         end
      end
      q = q_new
  end
# SHOULD NOT BE HERE
  return null
end


def trace(v, choice):
   choices = [choice]
   paren = v
   while paren do:
     choice, paren, _ = paren
     choices.push(choice)
   end
   choices.reverse_join
end

[tntxtnt]

BFS ăn gian ko chứng minh nếu ans có k chữ số, lỡ số lớn hơn 110…11 tới trước 101…11 và cả 2 cùng chia hết cho n thì sao :V Phải chứng minh nếu ans có k chữ số 0,1 và ans chia hết cho n thì ans là unique :V Edit: hay là phải cho chạy hết tới q.empty() luôn để xét mọi số có k chữ số và chia hết cho n để tránh trường hợp số lớn hơn tới trước :V

[rogp10]

BFS: số chữ số nhỏ hơn sẽ đến trước.
Prefix bé hơn sẽ đến trước: quy nạp từ “10” và “11”

Vậy là đúng rồi.

[tntxtnt]

vậy phải nói đây là Dijkatra mới đúng tuy ko xài heap

[rogp10]

Dijkstra khung sườn khá giống Breadth-first search nhưng BFS thì trọng số tất cả các cạnh bằng nhau.

[tntxtnt]

“Dijkstra” ở đây so sánh theo giá trị của số tạo thành mà :V Vì nó được insert theo đúng thứ tự bé tới lớn nên ko cần so sánh. Nhưng nếu insert theo thứ tự 1, 0 thay vì 0, 1 thì ko đúng :V

insert neighbor 0 rồi neighbor 1:
1 --> 10 11 --> 11 100 101 --> 100 101 110 111 --> …
đúng thứ tự bé tới lớn, ko cần so sánh

insert neighbor 1 rồi neighbor 0:
1 --> 11 10 --> 10 111 110 --> 111 110 101 100 --> …
sai thứ tự :V

nếu là BFS thì thứ tự neightbor đâu có quan trọng :V Ở đây buộc phải insert 0 rồi 1 :V

[rogp10]

Đúng thật trong bài này các con đường dù có độ dài bằng nhau cũng không hề giống nhau.

Cũng không hẳn, Dijkstra thì for v in u.neighbors(): tmp = shortest_so_far[u] + u.weight(v) mà.

[tntxtnt]

cái Dijkstra này weight ko nằm ở edge mà nằm ở vertex. Mỗi vertex có weight là giá trị của nó. Ví dụ n = 3 thì vert 1 có weight là 1, 10, 100

vd heap item này so sánh theo weight của nó: https://rextester.com/IMJT83011

import heapq

class Heap:
    class Item:
        def __init__(self, k, n):
            self.id = k % n
            self.weight = k
        def __lt__(self, other):
            return self.weight < other.weight
        def neighbors(self, n):
            yield Heap.Item(self.weight * 10 + 1, n)
            yield Heap.Item(self.weight * 10 + 0, n)

    def __init__(self, n):
        self.n = n
        self.q = [Heap.Item(1, self.n)]
        self.visited = [False] * self.n

    def solve(self):
        while self.q:
            u = heapq.heappop(self.q)
            if u.id == 0:
                return u.weight
            for v in u.neighbors(self.n):
                if not self.visited[v.id]:
                    self.q.append(v)
            self.visited[u.id] = True

print(','.join(str(Heap(i).solve()) for i in range(1, 35)))

nếu sửa dòng u = heapq.heappop(self.q) thành u = self.q.pop(0) thì nó sẽ trở thành BFS (queue dỏm, O(n) pop). Và vì neighbor 1 yield trước neighbor 0 nên n=27 nó ra kết quả sai: 1111111101, 1101111111 mới đúng: https://oeis.org/A004290/list. Nếu sửa lại cho nb 0 yield trước nb 1 thì bfs nó mới in ra kq đúng :V :V