पृष्ठभूमि:

मैं निम्नलिखित समस्याओं पर काम कर रहा हूं, "स्कीइंग चुनौतियां: प्रोग्रामिंग प्रोग्रामिंग प्रशिक्षण मैनुअल" से "द ट्रिप": स्कीइंग:

छात्रों का एक समूह एक क्लब का सदस्य है जो सालाना विभिन्न स्थानों पर यात्रा करता है। अतीत में उनके गंतव्यों में इंडियानापोलिस, फीनिक्स, नैशविले, फिलाडेल्फिया, सैन जोस और अटलांटा शामिल हैं। इस वसंत में वे आइंडहोवन की यात्रा की योजना बना रहे हैं।

समूह खर्चों को समान रूप से साझा करने के लिए पहले से सहमत है, लेकिन हर खर्च को साझा करना व्यावहारिक नहीं है क्योंकि यह होता है। इस प्रकार समूह के व्यक्ति भोजन, होटल, टैक्सी की सवारी और हवाई जहाज के टिकट जैसी विशेष चीजों के लिए भुगतान करते हैं। यात्रा के बाद, प्रत्येक छात्र का खर्च लंबा हो जाता है और पैसे का आदान-प्रदान होता है, ताकि प्रत्येक के लिए शुद्ध लागत एक प्रतिशत के भीतर हो। अतीत में, यह मुद्रा विनिमय थकाऊ और समय लेने वाला रहा है। आपका काम खर्चों की एक सूची से गणना करना है, सभी छात्रों की लागतों को बराबर करने के लिए (एक प्रतिशत के भीतर) धन की न्यूनतम राशि को बदलना होगा।

इनपुट

मानक इनपुट में कई यात्राओं की जानकारी होगी। से प्रत्येक यात्रा में एक रेखा होती है जिसमें धनात्मक पूर्णांक n होता है यात्रा पर छात्रों की संख्या। इसके बाद इनपुट की n लाइनें हैं, डॉलर और सेंट में एक छात्र द्वारा खर्च की गई प्रत्येक राशि। 1000 छात्रों से अधिक नहीं हैं और किसी भी छात्र ने इससे अधिक खर्च नहीं किया है $ 10,000.00 । एक एकल लाइन जिसमें 0 की जानकारी है पिछली यात्रा।

आउटपुट

प्रत्येक यात्रा के लिए, डॉलर और सेंट में धन की कुल राशि बताते हुए एक पंक्ति का उत्पादन किया जाता है, जिसे छात्रों की लागत को बराबर करने के लिए आदान-प्रदान किया जाना चाहिए।

(बोल्ड मेरा है, पुस्तक यहां, साइट यहाँ

मैंने निम्नलिखित कोड के साथ समस्या हल की है:

/*
 * the-trip.cpp
 */

#include <iostream>
#include <iomanip>
#include <cmath>

int main( int argc, char * argv[] )
{
    int students_number, transaction_cents;
    double expenses[1000], total, average, given_change, taken_change, minimum_change;
    while (std::cin >> students_number) {
        if (students_number == 0) {
            return 0;
        }
        total = 0;
        for (int i=0; i<students_number; i++) {
            std::cin >> expenses[i];
            total += expenses[i];
        }
        average = total / students_number;
        given_change = 0;
        taken_change = 0;
        for (int i=0; i<students_number; i++) {
            if (average > expenses[i]) {
                given_change += std::floor((average - expenses[i]) * 100) / 100;
            }
            if (average < expenses[i]) {
                taken_change += std::floor((expenses[i] - average) * 100) / 100;
            }
        }
        minimum_change = given_change > taken_change ? given_change : taken_change;
        std::cout << "$" << std::setprecision(2) << std::fixed << minimum_change << std::endl;
    }
    return 0;
}

मेरे मूल कार्यान्वयन में double के बजाय float था। यह विवरण के साथ प्रदान की गई छोटी समस्या के उदाहरणों के साथ काम कर रहा था और मैंने यह जानने में बहुत समय बिताया कि क्या गलत था।

अंत में मुझे पता चला कि मुझे double सटीक का उपयोग करना था, जाहिर है प्रोग्रामिंग चुनौती परीक्षणों में कुछ बड़े इनपुट ने फ्लोट के साथ मेरे एल्गोरिदम को विफल कर दिया।

प्रश्न:

यह देखते हुए कि इनपुट में १००० छात्र हो सकते हैं और प्रत्येक छात्र १०,००० डॉलर तक खर्च कर सकता है, मेरे total वैरिएबल को अधिकतम आकार के कई स्टोर करने होंगे 10,000,000 ।

मुझे कैसे तय करना चाहिए कि किस परिशुद्धता की आवश्यकता है? क्या ऐसा कुछ है जो मुझे संकेत देना चाहिए था कि फ्लोट इस कार्य के लिए पर्याप्त नहीं था?

मुझे बाद में एहसास हुआ कि इस मामले में मैं फ़्लोटिंग पॉइंट से बच सकता था क्योंकि मेरा नंबर पूर्णांक प्रकारों में फिट बैठता है, लेकिन मुझे अभी भी यह समझने में दिलचस्पी है कि अगर float पर्याप्त रूप से सटीक नहीं था ये मामला।

0
Andrea Casaccia 29 नवम्बर 2015, 17:20

3 जवाब

सबसे बढ़िया उत्तर

जैसा कि आपने कहा: पैसे का प्रतिनिधित्व करने के लिए कभी भी फ्लोटिंग पॉइंट वैरिएबल का उपयोग न करें। पूर्णांक निरूपण का उपयोग करना - या तो एक बड़ी संख्या में सेंट के रूप में या स्थानीय मुद्रा का अंश जो भी हो, या दो संख्याओं के रूप में [जो गणित को थोड़ा और अजीब बनाता है, लेकिन मान को देखने / पढ़ने / लिखने में दो के रूप में आसान होता है। इकाइयों ] ।

फ्लोटिंग पॉइंट का उपयोग न करने की प्रेरणा यह है कि यह "अक्सर सटीक नहीं होता है"। जैसे 1/3 को दशमलव प्रतिनिधित्व का उपयोग करके एक सटीक मान के रूप में नहीं लिखा जा सकता है, चाहे आप कितने भी लिखें, वास्तविक उत्तर में अधिक threes होंगे, बाइनरी फ़्लोटिंग पॉइंट मान कुछ दशमलव मानों का सटीक वर्णन नहीं कर सकते हैं, और आपको " 0.20 का आपका मान 0.20 से मेल नहीं खाता है, जो ग्राहक का बकाया है "- जिसका कोई मतलब नहीं है, लेकिन ऐसा इसलिए है क्योंकि" 0.200000000001 "और" 0.19999999999 "कंप्यूटर के अनुसार बिल्कुल समान नहीं हैं। और अंत में, उन छोटी गोल त्रुटियों से एक या किसी अन्य तरीके से कुछ बड़ी समस्या पैदा होगी - और इसकी परवाह किए बिना कि यह float, double या extra_super_long_double है।

हालांकि, अगर आपके पास इस तरह का सवाल है: अगर मुझे यूनिट के 1/100 वें हिस्से के प्रिज़न के साथ 10 मिलियन के मूल्य का प्रतिनिधित्व करना है, तो मुझे कितना बड़ा फ्लोटिंग पॉइंट वैरिएबल चाहिए, आपकी गणना हो जाती है:

float bigNumber = 10000000;
float smallNumber = 0.01;
float bits = log2(bigNumber/smallNumber);
cout << "Bits in mantissa needed: " << ceil(bits) << endl;

तो, इस मामले में, हमें बिट्स 29.897 के रूप में मिलते हैं, इसलिए आपको 30 बिट्स (दूसरे शब्दों में, float की आवश्यकता नहीं है)।

बेशक, अगर आपको डॉलर (या जो भी) के अंशों की आवश्यकता नहीं है, तो आप कुछ कम अंकों के साथ दूर हो सकते हैं। अर्थात् log2(10000000) = 23.2 - इसलिए मंटिसा के 24 बिट्स - & gt; अभी भी एक float के लिए बहुत बड़ा है।

1
Mats Petersson 29 नवम्बर 2015, 14:41

10,000,000> 2 ^ 23 ताकि आपको कम से कम 24 बिट्स मंटिसा की आवश्यकता हो, जो कि एकल परिशुद्धता प्रदान करता है। इंटरमीडिएट राउंडिंग के कारण, अंतिम बिट्स गलत कर सकते हैं।

1 अंक ~ 3.321928 बिट्स।

1
Yves Daoust 29 नवम्बर 2015, 14:33

क्या ऐसा कुछ है जो मुझे संकेत देना चाहिए था कि फ्लोट इस कार्य के लिए पर्याप्त नहीं था?

यह तथ्य कि बाइनरी फ्लोटिंग-पॉइंट (जो कि float और double दोनों का प्रतिनिधित्व नहीं करता है, यदि आप एक साधारण कंप्यूटर का उपयोग करते हैं) तो संकेत होना चाहिए था। बाइनरी फ्लोटिंग-पॉइंट उन भौतिक राशियों के लिए एकदम सही है, जो शुरू करने के लिए या संगणना के लिए गलत हैं, जो कि उचित समानता के साथ जो भी उचित संख्यात्मक प्रणाली है, वैसे भी गलत होंगे। मौद्रिक राशियों की सटीक गणना बाइनरी फ्लोटिंग-पॉइंट का अच्छा अनुप्रयोग नहीं है।

मुझे कैसे तय करना चाहिए कि किस परिशुद्धता की आवश्यकता है? ... मेरे कुल वेरिएबल को अधिकतम 10,000,000 की संख्या में स्टोर करना है।

सेंट की संख्या का प्रतिनिधित्व करने के लिए एक पूर्णांक प्रकार का उपयोग करें। अपने स्वयं के तर्क से, आपको 1,000,000,000 सेंट से अधिक की मात्रा से निपटना नहीं चाहिए, इसलिए long पर्याप्त होना चाहिए, लेकिन बस long long का उपयोग करें और अपने आप को कोने के मामलों के साथ परेशानी का जोखिम बचाएं।

3
Pascal Cuoq 29 नवम्बर 2015, 14:40