Thuật Toán Tối ưu: Số Siêu Nguyên Tố | VFO.VN

Forum

• 
• Diễn đàn
• Mới nhất
• Công nghệ
• Điện thoại
• Máy tính
• Xe
• Thủ Thuật
• Hỏi đáp

Đăng nhập News Feed

Tìm kiếm

Mọi thứ Chủ đề Diễn đàn này Chủ đề này Chỉ tìm trong tiêu đề Bởi: Tìm Tìm kiếm nâng cao… Menu Đăng nhập Đăng ký Install the app Cài đặt You are using an out of date browser. It may not display this or other websites correctly.You should upgrade or use an alternative browser.

• Lập Trình - Đồ họa - Web
• Lập trình
• Pascal

Thuật toán tối ưu: Số siêu nguyên tố

• ngoclamqb
• 7/12/17

thuật toán tối ưu nhất giải quyết bài toán này như thế nào vậy ạ Bài 7. Số siêu nguyên tố. (Đề thi HSG Thành phố) Số P gọi lầ số siêu nguyên tố, nếu nó nguyên tố và khi ta lần lượt bỏ các chữ số ở hàng đơn vị từ tái qua phải thì số mới nhận được vẫn là một số nguyên tố. Ví dụ: 239 là số siêu nguyên tố vì 239 là số nguyên tố và 23, 2 cũng là các số nguyên tố , còn 431 là số nguyên tô, 43 cũng là số nguyên tố, nhưng 4 không nguyên tố nên 431 không phải là số siêu nguyên tố. Cho một số n (0<n<10) Hãy đếm số lượng các số siêu nguyên tố có n chữ số .

Sửu Nguyễn

⭐️⭐️⭐️⭐️⭐️

Reply: thuật toán tối ưu nhất giải quyết bài toán này như thế nào vậy ạ Một dãy a[] = {1,2,3,5,7,9} là dãy các số con Chọn dãy này vì chắc chắn số đầu tiên phải là số nguyên tố Có số 1 vì số nguyên tố tận cùng là 1 cũng có thể là số siêu nguyên tố Từ dãy trên ta sẽ sắp xếp và check để kiểm tra số nguyên tố Bạn lập trình hay thi thuật toán không thôi để mình viết chi tiết cách của mình L

LanSG9x

Reply: thuật toán tối ưu nhất giải quyết bài toán này như thế nào vậy ạ +1 cho bạn 365 Designer. Em cũng nghĩ dựa vào dãy {1, 2, 3, 5, 7, 9} để xây dựng số nguyên tố từ ít chữ số tới nhiều chữ số. N

ngoclamqb

Reply: thuật toán tối ưu nhất giải quyết bài toán này như thế nào vậy ạ mình lập trình nhờ ban 365 designer cho mình xin thuật toán đi kèm cả code mình nghiên cứu để hiểu với ạ L

LanSG9x

Reply: thuật toán tối ưu nhất giải quyết bài toán này như thế nào vậy ạ Lần trước hỏi bạn đó cũng lặn. Em k biết Pascal. Em viết bằng C++ nha. Em thấy chuyển qua Pascal k khó đâu [ah] Mã: int n, a[4] = { 1, 3, 7, 9 }; void helper(int n, int s) { if (int(log10(s)) + 1 == n) printf("%d\n", s); else for (int i = 0; i < 4; i++) { int t = s * 10 + a[i]; if (prime(t)) // kiem tra t co phai la nguyen to k helper(n, t); } } int main() { n = 8; helper(n, 2); helper(n, 3); helper(n, 5); helper(n, 7); } [/ah] N

ngoclamqb

Reply: thuật toán tối ưu nhất giải quyết bài toán này như thế nào vậy ạ nt n, a[4] = { 1, 3, 7, 9 };//bạn nói rõ chỗ này mình với void helper(int n, int s) // số n và số s có ý nghĩa j bạn // { if (int(log10(s)) + 1 == n)//chỗ này là sao hả bạn printf("%d\n", s); // giải thích 2 chỗ này giùm mình else for (int i = 0; i < 4; i++) { //đây vòng lặp int t = s * 10 + a; if (prime(t)) // kiem tra t co phai la nguyen to k helper(n, t); }// đoạn này là một chương trình con đúng ko bạn Nói chung nhờ bạn giải thích dùm mình các lệnh trong đó với ạ để mình cs thể chuyển sang pascal dk L

LanSG9x

Cách làm của em là từ số nguyên tố có k chữ số, thêm 1 chữ số để tạo thành số nguyên tố có k+1 chữ số. Em bắt đầu bằng số nguyên tố có 1 chữ số, là 2, 3, 5, 7. Sau đó thêm vào những chữ số {1, 3, 7, 9} vì đó là những chữ số tận cùng của số nguyên tố. [ah] Mã: int n, // n chữ số a[4] = { 1, 3, 7, 9 }; // chữ số tận cùng của số nguyên tố có nhiều hơn 1 chữ số (mảng hằng) // n chữ số, s là số nguyên tố hiện tại. "helper" là chương trình con như bạn ghi void helper(int n, int s) { // nếu số nguyên tố hiện tại s có đủ n chữ số như đề yêu cầu thì in ra // số chữ số của 1 số nguyên dương s trong hệ cơ số 10 là: phần nguyên của log cơ 10 của s, sau đó +1 if (int(log10(s)) + 1 == n) printf("%d\n", s); // in ra số tìm được else // nếu không đủ n chữ số thì thêm các chữ số {1, 3, 7, 9} từ tập a for (int i = 0; i < 4; i++) { int t = s * 10 + a[i]; if (prime(t)) // kiem tra t co phai la nguyen to k helper(n, t); } } int main() { n = 8; helper(n, 2); // số nguyên tố bắt đầu là 2 helper(n, 3); // số nguyên tố bắt đầu là 3 helper(n, 5); // số nguyên tố bắt đầu là 5 helper(n, 7); // số nguyên tố bắt đầu là 7 } [/ah] N

ngoclamqb

cho mình hỏi 1 chút: 1.helper là một hàm hay thu tục vậy bạn 2.s số nguyên tố hiện tại chỗ này là như thế nào bạn giải thích rõ hơn 1 chút không ạ. 3.vì sao khi lấy phần nguyên cộng thêm 1 4. helper(n, t); cái này đệ quy lại hả bạn. 5.vì sao n =8 và gọi gọi ctc lại vói n và các số nguyên tố trên là như thế nào? nhờ bạn giải thích giùm L

LanSG9x

Bạn nên hiểu cái tư tưởng trước. Giả sử n = 3 (cần tìm các số siêu nguyên tố có 3 chữ số). - Bắt đầu là số nguyên tố 2, tức là helper(3, 2). Tức là s = 2. Em có t là {21, 23, 27, 29}. Như vậy chỉ có 23 và 29 thỏa mãn. Tiếp theo sẽ gọi helper(3, 23) và helper(3, 29). - Từ số nguyên tố 23 (tức là s=23), em có t là {231, 233, 237, 239}. Chỉ có 233, 239 là prime. Tiếp theo sẽ gọi helper(3, 233) và helper(3, 239) - Vì 233 và 239 đã có đủ 3 chữ số nên in ra 2 số này. - Tiếp theo quay lui xét số nguyên tố 29, em có t là {291, 293, 297, 299}. Chỉ có 293 là prime. Tiếp theo sẽ gọi helper(3, 293). - Vì 293 đã có đủ 3 chữ số nên in ra số này Như vậy những số siêu nguyên tố bắt đầu là 2 gồm: 233, 239, 293. - Tương tự em làm cho số siêu nguyên tố bắt đầu là 3, 5, 7. helper(3, 3), helper(3, 5), helper(3, 7) [ah] Mã: 21 (k prime) 231 (k prime) 23 -------------> 233 237 (k prime) 239 2 -------------> 27 (k prime) 291 (k prime) 29 -------------> 293 297 (k prime) 299 (k prime) [/ah] 1) helper là procedure theo ngôn ngữ Pascal 2) Bạn xem ví dụ trên sẽ hiểu s là gì 3) Cái này là công thức. Bạn Google xem số chữ số của 1 số nguyên dương được tính thế nào nha. 4) Đúng rồi, cái này là đệ quy 5) n=8 vì em cho ví dụ cho dễ làm. Chứ nhập xuất nhiều quá bạn đâu hiểu helper(n, 2), helper(n, 3), helper(n, 5), helper(n, 7) là bắt buộc vì em đang xét TẤT CẢ số nguyên tố bắt đầu từ 2, 3, 5, 7 Thực ra số n k cần đưa vào helper cũng được vì nó là biến toàn cục rồi Đăng nhập bằng tài khoản VFO hoặc Facebook Google

Bài viết mới nhất

• Kho truyện ngắn cực hay
  • shopoga
  • 19:14 Hôm qua
• Sách Hay Mỗi Ngày
  • shopoga
  • 19:06 Hôm qua
• góc hỏi
  • vượng nguyễn 06
  • 11:33 Hôm qua
• Máy tính problem
  • vượng nguyễn 06
  • 11:31 Hôm qua
• cpu
  • vượng nguyễn 06
  • 11:26 Hôm qua

Bài viết đang hot

• máy tính
  • đuc trongscmt
  • 08:00 Hôm qua
• góc hỏi
  • DuongTho
  • 08:19 Hôm qua
• Điện thoại
  • Khuất duy vũ
  • 08:13 Hôm qua
• Câu hỏi về phát triển công nghệ
  • vượng nguyễn 06
  • 07:50 Hôm qua
• máy tính
  • Phan Danh Thành Đạt
  • 08:23 Hôm qua

Thống kê

Chủ đề 102,018 Bài viết 469,509 Thành viên 340,341 Thành viên mới nhất ttplus

Bài viết được quan tâm nhiều

• T Huawei ra mắt Mate X6 tại thị trường quốc tế
  • Tin Tức
  • 08:54, Chủ nhật
• T Lộ diện ảnh thực tế và thông tin phần cứng Honor GT
  • Tin Tức
  • 08:27, Chủ nhật
• Trải nghiệm thực tế chuột chơi game Razer Viper V3 Pro
  • Tuấn Hà
  • 17:50, Chủ nhật
• T Lộ diện thông số kỹ thuật Google Pixel 9a
  • Tin Tức
  • 07:55, Chủ nhật
• T HMD Global ra mắt hai chiếc điện thoại Nokia 105 4G và 110 4G
  • Tin Tức
  • 10:45, Thứ hai

Top