HW1.5 - Finding a matching image - 题目

A program compares a newly scanned picture with a collection of stored pictures. A picture is represented by an array of integers: each element gives the brightness of one small square, called a pixel, from 0 for black through 255 for white. All pictures have the same size, and corresponding array indices refer to the same location in each picture.

For this task, the difference between two pictures is the sum of the absolute brightness differences at corresponding pixels. The following function computes that number. Assume int is a 32-bit signed type and 100 <= n <= 1000000. All of this function’s arithmetic then fits in int.

int image_distance(int *a, int *b, int n) {
    int total = 0;
    for (int i = 0; i < n; ++i) {
        int change = a[i] - b[i];
        if (change < 0) change = -change;
        total += change;
    }
    return total;
}

The program must return the stored picture with the smallest difference from the new picture. Each picture has a permanent integer ID; among equally close stored pictures, choose the smaller ID. Pictures stay unchanged throughout this problem.

A complete comparison examines all n pixels. Doing that for thousands of pictures can take substantial work. Suppose at least one stored picture has been fully compared, and best is the smallest complete difference found so far. While comparing another picture, the program can see the running sum for the pixels examined so far. It would like to avoid reading pixels whose values cannot affect which picture it chooses.

A quick estimate. Before doing full comparisons, the program can examine the first 100 pixels of each stored picture and multiply that partial difference by n / 100. Treat this multiplication as real-number arithmetic; rounding is not the issue.

This is an estimate of the full difference. The first 100 pixels may cover an unusual part of a picture; there is no guarantee that their average difference represents the rest. The estimate costs work to calculate, but much less than a full comparison when n is large. The requirement is still to return the exact closest picture.

Finding all close matches. The program also has a mode that shows every picture whose full difference is at most a chosen limit L. Unlike choosing one closest picture, this mode only needs to decide which pictures qualify; it does not need to display their exact differences.

During a comparison, the program knows how many pixels it has examined and their partial difference. It knows nothing about the unread pixel values beyond the brightness range 0 through 255 stated above.

提交

Written answers receive AI rubric assessment.

Up to 3 submission attempts per student. Sign in to see your remaining attempts.

Each submission includes all questions. Review your answers before submitting.

Short explanations are welcome. You may leave answers blank; unanswered questions receive zero credit.

1. Describe a rule for stopping a picture comparison before all its pixels have been examined, while preserving the required closest-picture result. Explain what lets your rule make a decision despite the unread pixels. (40 points)Your answer

2. How could the quick estimates help reduce the work of finding the exact closest picture? Describe how you would use them and what you would still need to check before deciding the answer. (30 points)Your answer

3. In the "find all close matches" mode, when could the program accept a picture as a match before reading all its pixels? Describe the guarantee you would need about the unread part and how the known brightness range could provide it. (30 points)Your answer

Drafts are saved in this browser every 30 seconds.

C++ Online Judge

C++

2026 Fall HW1

G. HW1.5 - Finding a matching image

提交