प्रौद्योगिकी साझेदारी

Touge Resource Library (24) प्लस् चिह्नं सम्मिलितं कुर्वन्तु

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

1. समस्यावर्णनम्

2. एल्गोरिदमिक विचार  

एतस्याः समस्यायाः समाधानार्थं गतिशीलप्रोग्रामिंग् इत्यस्य उपयोगः कर्तुं शक्यते ।

प्रथमं, संख्यातारं बहुषु सङ्ख्यासु विभज्य, प्रत्येकं सङ्ख्यां संग्रहीतुं array nums इत्यस्य उपयोगं कुर्वन्तु । यथा, 79846 इति सङ्ख्यातारं [7, 9, 8, 4, 6] इति सरणीयां विभक्तं भविष्यति ।

ततः द्वि-आयामी सरणी dp परिभाषयन्तु, यत्र dp[i][j] न्यूनतमं मूल्यं प्रतिनिधियति यत् प्रथमेषु i संख्यासु j plus चिह्नानि सम्मिलितं कृत्वा प्राप्तुं शक्यते । dp[0][0] = 0 इत्येतत् विहाय dp सरणीम् अनन्तं यावत् आरभत ।

ततः dp एरे अपडेट् कर्तुं द्वौ लूप् उपयुज्यताम् । बाह्यपाशः संख्यातारस्य प्रत्येकं सङ्ख्यां भ्रमति, अन्तः पाशः च प्रविष्टानां प्लस् चिह्नानां संख्यां भ्रमति । प्रत्येकस्य dp[i][j] कृते, भवान् nums[i] सङ्ख्यां पूर्वसङ्ख्यायाः सह संयोजयित्वा नूतना संख्यां निर्मातुं, अथवा nums[i] सङ्ख्यायाः पूर्वसङ्ख्यायाः च मध्ये प्लस् चिह्नं सम्मिलितुं विचारयितुं शक्नोति द्वयोः प्रकरणयोः लघुतरं मूल्यं dp[i][j] इत्यस्य मूल्यत्वेन गृह्यताम् ।

अन्ते dp सरणीयाः अन्तिमपङ्क्तौ न्यूनतमं मूल्यं न्यूनतमं मूल्यं अन्विष्यते ।

3. संहिता कार्यान्वयनम्  

  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <limits.h>
  4. #include <stdlib.h>
  5. // Helper function to extract integer value from substring
  6. int getNumber(char* str, int start, int end) {
  7. char buffer[12]; // Buffer large enough for max 10 digits + '0'
  8. int length = end - start + 1;
  9. strncpy(buffer, str + start, length);
  10. buffer[length] = '0';
  11. return atoi(buffer);
  12. }
  13. int main() {
  14. char str[201];
  15. int M;
  16. scanf("%s %d", str, &M);
  17. int n = strlen(str);
  18. int dp[n+1][M+1];
  19. // Initialize dp array with large numbers
  20. for (int i = 0; i <= n; i++) {
  21. for (int j = 0; j <= M; j++) {
  22. dp[i][j] = INT_MAX;
  23. }
  24. }
  25. // Base case: no splits
  26. dp[0][0] = 0;
  27. // Dynamic programming to calculate minimum sum
  28. for (int i = 1; i <= n; i++) {
  29. for (int j = 0; j <= M; j++) { // j can be 0 as well
  30. if (j == 0) {
  31. dp[i][j] = getNumber(str, 0, i-1);
  32. } else {
  33. for (int k = 1; k < i; k++) { // k starts from 1
  34. if (dp[k][j-1] != INT_MAX) {
  35. int num = getNumber(str, k, i-1);
  36. if (dp[k][j-1] + num < dp[i][j]) {
  37. dp[i][j] = dp[k][j-1] + num;
  38. }
  39. }
  40. }
  41. }
  42. }
  43. }
  44. // Find the minimum value in dp[n][*] with M splits
  45. int result = INT_MAX;
  46. for (int i = 0; i <= M; i++) {
  47. if (dp[n][i] < result) {
  48. result = dp[n][i];
  49. }
  50. }
  51. printf("%dn", result);
  52. return 0;
  53. }

परिणामाः

 निगमन       

उत्साहवर्धनस्य इच्छा

धैर्यं पर्वतानाम् स्निग्धं कर्तुं शक्नोति

!!!