อยากต่อสู้กับปีศาจและเรียนรู้เทมเพลต C++ ไหม แก้ปัญหานี้.

ในขณะที่เรียนรู้ C++ คุณได้พบกับเทมเพลตที่เป็นวิธีที่ยอดเยี่ยมในการสร้างฟังก์ชันและคลาสทั่วไป แต่มันคือ C++ มาเลย คุณสามารถทำได้มากกว่านั้น เทมเพลต C++ เป็นเพื่อนของฉัน อย่าหยุดอยู่เพียงคลาสและฟังก์ชันเท่านั้น มันเป็นอีกโลกหนึ่ง โลกแห่งการเขียนโปรแกรมเมตาเทมเพลต แต่อย่างไรก็ตาม คุณเพียงต้องการใช้เทมเพลต C++ ให้เก่ง ไม่ต้องกังวล ฉันจะเสนอปัญหาเทมเพลต C++ ที่เหมาะสมให้กับคุณ ซึ่งเรียกว่า "Peano Numbers"

คุณสามารถแก้ปัญหาได้ที่นี่ "หมายเลข Peano"

ก่อนอื่น อย่า google อย่า stackoverflow อย่า chatgpt-it อย่าเขียนโค้ด llama ยังไงก็เข้าใจ
ลองด้วยตัวเอง เสียเวลาจนกว่าคุณจะสร้างมันขึ้นมา หรืออับอายแล้วตรวจสอบวิธีแก้ปัญหา

สารละลาย

คุณยอมแพ้เหรอ? 😒

คิดวิธีแก้ปัญหาไม่ได้ใช่ไหม? ยอดเยี่ยม

ไม่ต้องละอายใจที่จะลอง ฉันก็ประสบปัญหานี้เหมือนกัน

ดังนั้นเราจึงมีจุดเริ่มต้น

struct Peano {};
struct Zero: Peano {};
template<class T>
struct Succ: Peano {};

ซึ่งคล้ายกับ 0 และตัวเลขที่มากกว่าหรือเท่ากับ 1 เพื่อให้เราสามารถแทนตัวเลขใดๆ ได้
เรามาแจกแจงรายละเอียดนี้และมุ่งเน้นไปที่ส่วนเล็กๆ เนื่องจากฉันใช้แบบเทมเพลต ก่อนอื่นฉันต้องมีความคิดว่าจะเกิดอะไรขึ้น และฉันจะแก้ไขปัญหาอย่างไร

การดำเนินการเพิ่ม

template <class T1, class T2> struct Add {};

แล้วตอนนี้ฉันจะทำสิ่งนี้ได้อย่างไร? ฉันไม่สามารถใช้ตัวดำเนินการหรือจำนวนเต็มในตัวได้
ฉันต้องพึ่งพาเทมเพลตที่ C++ นำเสนอ
เอาล่ะ คุณ เทมเพลต C++ :

• คุณสามารถทำความเชี่ยวชาญด้านเทมเพลตได้
• คุณสามารถทำตัวเหมือนการจับคู่รูปแบบแต่สำหรับประเภท
• คุณสามารถทำการเรียกซ้ำได้

เนื่องจากฉันไม่สามารถใช้โอเปอเรเตอร์ได้ ฉันจึงมีข้อจำกัดอย่างมาก ดังนั้นฉันจึงต้องใช้ความคิดสร้างสรรค์ในเรื่องนี้ ฉันรู้ว่าฉันต้องมีการเรียกซ้ำเพื่อทำซ้ำการดำเนินการและความเชี่ยวชาญพิเศษของเทมเพลต เพื่อสร้างข้อยกเว้นว่าคอมไพลเลอร์ควรทำงานอย่างไรเมื่อเป็นไปตามเกณฑ์ที่กำหนด

มาดูกันว่าฉันจะใช้ความเชี่ยวชาญพิเศษของเทมเพลตได้อย่างไร ตามปัญหา 1 และ 0 จะแสดงเป็น 'Succ‹Zero›' และ 'ศูนย์' เราสามารถรวมได้มากเท่ากับ 'Succ' เท่าที่เราสามารถทำได้เพื่อแสดงตัวเลข นั่นคือการบวกพื้นฐานด้วย 1 แล้วการลบด้วย 1 ล่ะ?

ฉันเดาว่าฉันสามารถทำตรงกันข้ามและแกะหมายเลขภายในได้

template <class T1, class T2> struct Add {};
template <class T1, class T2> struct Add<T1, Succ<T2>> {};

ตอนนี้เรามี T1 ซึ่งเป็นตัวเลข และ T2 ซึ่งเป็นตัวเลข-1 อีกตัว
ฉันเห็นบางอย่างอยู่ตรงนี้ เมื่อคุณลองคิดดู ฉันสามารถแสดงการบวกเป็นการลบ 1 จากตัวถูกดำเนินการทางขวา และเพิ่ม 1 ไปทางตัวถูกดำเนินการทางซ้ายได้

จะเป็นอย่างไรถ้าฉันบวก 1 และลบ 1 ต่อไปจนกระทั่งตัวถูกดำเนินการที่ถูกต้องคือ 'ศูนย์' ฉันคิดว่าฉันเข้าใจแล้ว เมื่อเทมเพลต C++ เป็นแบบเรียกซ้ำ ฉันสามารถเรียกการดำเนินการเดิมซ้ำแล้วซ้ำอีกโดยทำหน้าที่เป็นลูปได้
เยี่ยมมาก

template <class T1, class T2> struct Add {};
template <class T1, class T2> struct Add<T1, Succ<T2>> {
 using type = typename Add<Succ<T1>, T2>::type;
};

การเรียกซ้ำแบบ Woopse โดยไม่มีจุดหยุด ใช่แล้ว… มาเพิ่มจุดที่มันควรหยุดกันดีกว่า

เนื่องจากเราไม่ได้จัดการกับจำนวนลบ เราจึงสามารถหยุดได้เมื่อตัวถูกดำเนินการตัวที่สองเป็นศูนย์

template <class T1, class T2> struct Add {};
template <class T1, class T2> struct Add<T1, Succ<T2>> {
 using type = typename Add<Succ<T1>, T2>::type;
};
template <class T1> struct Add<T1, Zero> {
 using type = T1;
};

และตอนนี้ถึงเวลาสำหรับการทดสอบจริง
C++ มีชุดยูทิลิตี้สำหรับการจัดการกับเทมเพลตที่กำหนดไว้ในส่วนหัว '‹type_traits›'
ในส่วนหัว type_traits ฉันต้องการ “std::is_same_v‹T1, T2›” ซึ่งตรวจสอบว่า T1 และ T2 เป็นประเภทเดียวกันหรือไม่และส่งคืนค่าจริงหรือเท็จ

#include <type_traits>
#include <iostream>
template <class T1, class T2> struct Add {};
template <class T1, class T2> struct Add<T1, Succ<T2>> {
 using type = typename Add<Succ<T1>, T2>::type;
};
template <class T1> struct Add<T1, Zero> {
 using type = T1;
};
int main() {
 using One = Succ<Zero>;
 using Two = Succ<One>;
 using Three = Succ<Two>;
 std::cout << std::is_same_v<typename Add<One, One>::type, Two> << '\n'; // compare two types
 std::cout << std::is_same_v<typename Add<Two, One>::type, Three> << '\n';
 std::cout << std::is_same_v<typename Add<One, Three>::type, Two> << '\n';
}

การคอมไพล์และรันโค้ดต่อไปนี้ทำให้เรา:

1
1
1

1 สำหรับ true และ 0 สำหรับ false (เราสามารถใช้ std::boolalpha เพื่อส่งออกค่าบูลีนแทน)
จนถึงตอนนี้ ! เจ๋งทุกอย่างใช้งานได้ ตอนนี้ด้วยความคิดนั้น ฉันสามารถทำการคูณและลบเพื่อทำงาน และการหารเป็นเพียงลำดับการลบเลขคี่และเลขคู่ ตัดสินและไปไกลถึงการดำเนินการทางคณิตศาสตร์ทั้งหมด แคลคูลัส พีชคณิต กลศาสตร์ควอนตัมด้วย

การดำเนินการลบ

เอาล่ะ มาลองลบกัน ปัญหาแนะนำให้เราตรวจสอบข้อผิดพลาดในกรณีที่ผลลัพธ์เป็นลบ

template <class T1, class T2> struct Sub {};

นอกจากนี้ ฉันยังคงพันตัวถูกดำเนินการทางซ้ายใน Succ N ครั้ง จนกระทั่งตัวถูกดำเนินการที่สองถึงศูนย์
สำหรับการลบ ฉันสามารถทำได้เช่นเดียวกัน แต่ด้วยการแกะตัวถูกดำเนินการทางซ้าย N ครั้ง จนกระทั่งตัวถูกดำเนินการที่สองถึงศูนย์

template <class T1, class T2> struct Sub {};
template <class T1, class T2> struct Sub<Succ<T1>, Succ<T2>> {
 using type = typename Sub<T1, T2>::type;
};
template <class T1> struct Sub<T1, Zero> {
 using type = T1;
};

แต่ฉันต้องจัดการกรณีที่ตัวถูกดำเนินการตัวแรกถึงศูนย์ก่อนตัวถูก โดยการเพิ่มประเภทข้อผิดพลาดและตั้งค่าเป็นลบเมื่อตัวถูกดำเนินการที่ 1 เป็นศูนย์และ NoError เมื่อการดำเนินการสามารถเสร็จสิ้นโดยไม่มีข้อผิดพลาด

template <class T1, class T2> struct Sub {};
template <class T1, class T2> struct Sub<Succ<T1>, Succ<T2>>: Sub<T1, T2> {};
template <class T1> struct Sub<T1, Zero> {
 using error = NoError;
 using type = T1;
};
template <class T2> struct Sub<Zero, Succ<T2>> {
 using error = Negative;
};

ครั้งนี้ฉันใช้คลาสย่อยและไม่ได้ระบุ `type` อย่างชัดเจนเพราะฉันไม่ต้องการระบุค่าเมื่อมีข้อผิดพลาดเชิงลบ
ตอนนี้เรามาดูกันว่าจะแสดงผลลัพธ์ที่ถูกต้องหรือไม่

#include <ios>
#include <type_traits>
template <class T1, class T2> struct Sub {};
template <class T1, class T2> struct Sub<Succ<T1>, Succ<T2>>: Sub<T1, T2> {};
template <class T1> struct Sub<T1, Zero> {
 using error = NoError;
 using type = T1;
};
template <class T2> struct Sub<Zero, Succ<T2>> {
 using error = Negative;
};
int main() {
 using One = Succ<Zero>;
 using Two = Succ<One>;
 using Three = Succ<Two>;
 using Four = Succ<Three>;
std::cout << std::boolalpha;
 std::cout << std::is_same_v<typename Sub<One, One>::type, Zero> << '\n';
 std::cout << std::is_same_v<typename Sub<Two, One>::type, One> << '\n';
 std::cout << std::is_same_v<typename Sub<Four, Two>::type, Two> << '\n';
 std::cout << std::is_same_v<Sub<Zero, Two>::error, Negative> << '\n';
}
true
true
true
true

และมันได้ผล!

การดำเนินการคูณ

ทีนี้สำหรับการคูณบิ๊กบอย คุณก็รู้แล้วว่ามาเขียนการคูณเป็นการบวกกันดีกว่า
4 * 3 คือ 4 + 4 + 4
5 * 7 คือ 5 + 5 + 5 + 5 + 5 + 5 + 5
2 * 4 คือ 2 + 2 + 2 + 2
ฉันเห็นรูปแบบตรงนี้ เราเก็บตัวถูกดำเนินการตัวแรกให้คงที่และเพิ่มเข้าไปในตัวมันเอง N ครั้ง (N = ค่าของตัวถูกดำเนินการตัวที่สอง) ดูเหมือนว่าการบวกและการลบ
มาเขียนมันในฟังก์ชันกันดีกว่า

int multiply(int a, int b) {
 int c = a;
 for(int i = 1; i < b; ++i) {
 c += a;
 }
 return c;
}

ใช้งานได้ดีแต่เราไม่สามารถมี for loops ในเทมเพลตได้ ทั้งหมดที่เรามีคือการเรียกซ้ำ ลองใช้การเรียกซ้ำแทน

int multiply(int a, int b) {
 if(b == 1) return a;
 return a + multiply(a, b - 1);
}
// multiply(4, 3) => 4 + multiply(4, 2) => 4 + 4 + multiply(4, 1) => 4 + 4 + 4 = 12

อย่างไรก็ตาม การใช้งานนี้อาจทำการคำนวณมากกว่าที่จำเป็นหาก b หรือ a เป็น 0

int multiply(int a, int b) {
 if(b == 1) return a;
 if(b == 0) return 0;
 return a + multiply(a, b - 1);
}
// or even better
int multiply(int a, int b) {
 if(b == 0 || a == 0) return 0;
 return a + multiply(a, b - 1);
}

การแปลสิ่งนี้ในเทมเพลต C ++ ให้

#include<type_traits>
template <class T1, class T2> struct Mul {};
template <class T1, class T2> struct Mul<T1, Succ<T2>> {
 using type = std::conditional_t<std::is_same_v<T1, Zero>, Zero, typename Add<T1, typename Mul<T1, T2>::type>::type>; // std::condtitional_t here works like if(a == 0) return 0
};
// if (b == 0) return 0
template <class T1> struct Mul<T1, Zero> {
 using type = Zero;
};

การทดสอบ

#include<type_traits>
#include<ios>

template <class T1, class T2> struct Mul {};
template <class T1, class T2> struct Mul<T1, Succ<T2>> {
 using type = std::conditional_t<std::is_same_v<T1, Zero>, Zero, typename Add<T1, typename Mul<T1, T2>::type>::type>; // std::condtitional_t here works like if(a == 0) return 0
};
// if (b == 0) return 0
template <class T1> struct Mul<T1, Zero> {
 using type = Zero;
};

int main() {
 using One = Succ<Zero>;
 using Two = Succ<One>;
 using Three = Succ<Two>;
 using Four = Succ<Three>;

 std::cout << std::boolalpha;
 std::cout << std::is_same_v<typename Mul<One, One>::type, One> << '\n';
 std::cout << std::is_same_v<typename Mul<Two, One>::type, Two> << '\n';
 std::cout << std::is_same_v<typename Mul<Four, Zero>::type, Zero> << '\n';
 std::cout << std::is_same_v<typename Mul<Zero, Zero>::type, Zero> << '\n';
 std::cout << std::is_same_v<typename Mul<Zero, Two>::type, Zero> << '\n';
 std::cout << std::is_same_v<typename Mul<Two, Two>::type, Four> << '\n';
}

การรวบรวมสิ่งนี้ทำให้เรา

true
true
true
true
true
true

???

นี่เป็นตอนที่ 1 และหากคุณยังคิดไม่ออก คุณอาจลองแก้ไขส่วนที่เหลือด้วยตัวเอง