diff options
| -rw-r--r-- | sonstiges/Roman.cpp | 40 | ||||
| -rw-r--r-- | sonstiges/bitOps.cpp | 22 | ||||
| -rw-r--r-- | sonstiges/sonstiges.tex | 6 | ||||
| -rw-r--r-- | toDo.txt | 4 |
4 files changed, 69 insertions, 3 deletions
diff --git a/sonstiges/Roman.cpp b/sonstiges/Roman.cpp new file mode 100644 index 0000000..195f833 --- /dev/null +++ b/sonstiges/Roman.cpp @@ -0,0 +1,40 @@ +map<char,int> m; map<int,char> o; +int num[7] = {1000,500,100,50,10,5,1}; + +void buildMap() { + m['M'] = 1000; m['D'] = 500; m['C'] = 100; m['L'] = 50; m['X'] = 10; m['V'] = 5; m['I'] = 1; m[' '] = 0; + o[1000] = 'M'; o[500] = 'D'; o[100] = 'C'; o[50] = 'L'; o[10] = 'X'; o[5] = 'V'; o[1] = 'I'; +} + +int convertToInt(string &s) { + int res = m[s[0]]; + for(int i = 1; i < s.size(); i++) { + if(m[s[i-1]] < m[s[i]]) + res -= 2*m[s[i-1]]; + res += m[s[i]]; + } + return res; +} + +string convertToRoman(int n) { + string roman = ""; + for(int i = 0; i < 7; i++) { + while(n >= num[i]) { + roman += o[num[i]]; + n -= num[i]; + } + } + int pos = roman.find("CCCC"); + if(pos != string::npos) roman.replace(pos,4,"CD"); + pos = roman.find("XXXX"); + if(pos != string::npos) roman.replace(pos,4,"XL"); + pos = roman.find("IIII"); + if(pos != string::npos) roman.replace(pos,4,"IV"); + pos = roman.find("DCD"); + if(pos != string::npos) roman.replace(pos,3,"CM"); + pos = roman.find("LXL"); + if(pos != string::npos) roman.replace(pos,3,"XC"); + pos = roman.find("VIV"); + if(pos != string::npos) roman.replace(pos,3,"IX"); + return roman; +} diff --git a/sonstiges/bitOps.cpp b/sonstiges/bitOps.cpp new file mode 100644 index 0000000..df8cd8f --- /dev/null +++ b/sonstiges/bitOps.cpp @@ -0,0 +1,22 @@ +[lsb: 0-th bit, msb: n-th bit,] + +Get j-th bit: +(a & (1 << j)) != 0 + +Set j-th bit: +a |= (1 << j) + +Clear j-th bit: +a &= ~(1 << j) + +Toggle j-th bit: +a ^= (1 << j) + +Get value of first set bit: +(a & -a) + +Turn on all bits: +a = -1 + +Turn on first n bits: +a = (1 << n) - 1 diff --git a/sonstiges/sonstiges.tex b/sonstiges/sonstiges.tex index 375dc6b..8960a8a 100644 --- a/sonstiges/sonstiges.tex +++ b/sonstiges/sonstiges.tex @@ -16,3 +16,9 @@ Wenn die Eingabe aus einem kleinen Intervall $\left[0, n\right)$ stammt ist Buck \subsubsection{LSD-Radixsort} \lstinputlisting{sonstiges/radixsort.cpp} + +\subsubsection{Bit Operations} +\lstinputlisting{sonstiges/bitOps.cpp} + +\subsubsection{Roman-Literal-Converting} +\lstinputlisting{sonstiges/Roman.cpp} @@ -1,6 +1,4 @@ - bitonic tsp - josephus problem - min cost max flow -- roman numerals -- NIM GAMES (WICHTIG) -- bit operationen (WICHTIG)
\ No newline at end of file +- bit operationen (WICHTIG) |